[LeetCode] 2. Add Two Numbers - Java

Add Two Numbers - LeetCode

 

문제

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

 

두 개의 연결 리스트가 주어졌을 때, 이 두 연결 리스트가 나타내는 두 개의 정수를 더하는 문제이다.

각 연결 리스트의 노드는 한 자리 숫자를 나타내며, 두 연결 리스트를 더한 결과를 연결 리스트 형태로 반환해야 한다.

 

---

 

내 풀이

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dHead = new ListNode(0);
        ListNode curr = dHead;
        int carry = 0;

        while(l1 != null || l2 != null){
            int sum = carry;
            if(l1 != null){
                sum += l1.val;
                 l1 = l1.next;
            }
            if(l2 != null){
                sum += l2.val;
                 l2 = l2.next;
            }            

            carry = sum/10;
            curr.next = new ListNode(sum%10);
            curr = curr.next;

        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return dHead.next;
    }
}

 

• dHead 노드 : 결과 리스트의 시작 부분을 나타내기 위해 가상의 노드를 생성
• curr 포인터 : 결과 리스트를 생성하면서 현재 위치를 나타내는 포인터
• carry : 자리 올림 값

 

루프에서 두 연결리스트를 순회하면서 값을 더하고 carry를 처리한다.

결과 연결리스트에는 현재 자릿수에 해당하는 값만 저장되므로 carry를 10으로 나눈 나머지를 저장해준다.

루프가 끝나면 마지막 남아있을 수 있는 carry 값을 처리해준다.

dHead.next 부터 실제 결과 노드들이 시작되므로 dHead.next를 반환해준다.

 

• 시간복잡도 : O(n) - 두 연결리스트의 노드들을 한 번씩 순회
• 공간복잡도 : O(n) - 새로운 연결리스트를 생성하는 과정에서 사용되는 공간

 

자릿수를 처리하는 것이 조금 헷갈려서 시간이 꽤 소요되었다.

리스트의 마지막에 값이 삽입될 때 노드의 값과 포인터를 어떤식으로 업데이트 해줘야하는지 확실히 공부할 수 있었다.