2. Add Two Numbers

Add Two Numbers

(https://leetcode.com/problems/add-two-numbers/)

---

두 개의 리스트 노드를 입력 받아, 각 리스트 노드의 값을 더한 새로운 리스트 노드를 생성하는 문제입니다. 일반적으로 생각할 때 단순히 두 개의 리스트 노드를 순회하면서 진행하면 될 것 같지만, 더할 때 10을 넘어가면 일반 덧셈 처럼 뒤 값에 해당 몫을 더해주어야 합니다.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

위와 같은 예에서 가장 마지막 노드의 값이 7이 아닌 8인 이유도 그때문입니다. (Explanation 에서 설명하는 덧셈 로직과 같습니다.)

 

알고리즘 이라기 보다는 구현 문제라고 보면 됩니다. 자바로 구현하면 아래와 같습니다.

public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(0);
        ListNode dummy = l3;
        int sum = 0;
        int carry = 0;
        int lval1 = 0;
        int lval2 = 0;

        while (l1 != null || l2 != null) {

            if (l1 == null) {
                lval1 = 0;
            } else {
                lval1 = l1.val;
            }

            if (l2 == null) {
                lval2 = 0;
            } else {
                lval2 = l2.val;
            }

            sum = lval1 + lval2 + carry;
            if (sum >= 10) {
                carry = sum / 10;
            } else {
                carry = 0;
            }

            l3.next = new ListNode(sum % 10);
            l3 = l3.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        if (carry > 0) {
            l3.next = new ListNode(carry);
        }
        return dummy.next;
    }
}

처음에 설명했듯이 단순히 리스트 노드 두 개를 동시에 순회하면서 그 값이 10을 넘으면 그 몫을 carry 로, 나머지를 sum 으로 하고 새로운 노드를 생성하면 됩니다.

 

다만, 리스트 노드 두 개를 순회하면서 생기는 예외 (예를 들면 하나의 리스트 노드가 나머지 보다 더 길다던지) 들을 위해서 로직 자체를 각각 리스트 노드만 순회할 수도 있지만 하나에서 처리 하기 위해 노드가 null 이면 임의로 값 0으로 바꿔주는 것을 추가하였습니다. 마찬가지의 이유로 다음 노드를 가르킬 때 각각 null 체크도 해 주었습니다.

 

carry 에 관하여 따로 처리해준 이유는 5 + 5 가 10인 이유와 같습니다. 만약 carry 에 대한 처리를 추가로 해주지 않으면 값은 0 만 되겠죠.

 

값을 업데이트한 리스트 노드 l3 가 아니라 dummy.next 를 한 이유는 이미 리스트 노드 l3는 끝까지 순회했기 때문입니다. (포인터가 이미 마지막에 다다름) 우리가 리턴해야 하는 리스트 노드는 처음 부터 시작해야 하기 때문에 l3 와 같은 객체인 dummy 를 리턴하되, null 을 피하기 위해서 초기에 가짜 값 0을 넣었던 노드는 제외해야 하기 때문에 dummy.next 를 리턴한 것입니다.

 

LeetCode 의 링크드 리스트 문제는 대부분 이와 같이 솔루션이 구성되어있고, 실제로 이렇게 해야 답안이 훨씬 심플해지므로 이런 방식은 자주 쓰여집니다.

 

난이도는 medium 이지만 easy 에 가까운 구현 문제라고 생각됩니다.

시간 복잡도는 두 개의 리스트 노드의 길이 n, m 이 있을 때 O(n+m)이 되겠죠.