문제

비어있지 않은 두 LinkedList가 존재한다. 이 리스트에는 각 0~9의 숫자를 저장하는 노드들이 이어져있는데 노드의 역방향으로 숫자들을 이어붙인 숫자가 원래 숫자이다. 즉 342는 LinkedList의 노드들이 2 → 4 → 3 순으로 이어져있다. 이 문제는 각 LinkedList가 나타내는 원래 숫자를 더한 것을 같은 형식의 LinkedList로 반환하는 것이다.

즉 342(2 → 4 → 3)와 465(5 → 6 → 4)를 더한 결과인 807을 7 → 0 → 8 형태로 LinkedList를 만들어 반환하는 것이다.

문제에서 주어진 LinkedList의 구현은 다음과 같다.

// 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; }
}

풀이

문제가 어렵게 쓰여져있는데 쉽게 생각하면 일반적인 두 자연수의 합을 계산하는 방식과 동일하다. 1의 자리부터 더해가면서 올림이 생기면 올려주어 계산하면 된다.

먼저 결과를 반환할 LinkedList(result)를 생성한 후 l1과 l2를 한 칸씩 옮기면서 result의 다음 노드에 들어갈 값을 계산하고 result.next에 새로운 노드를 이어준다. 그 다음 result 또한 한 칸 옮겨준다. 이 과정에서 만약 result의 head를 따로 저장해놓지 않고 단순히 result를 return하면 안된다. result를 리턴한다면 tail에 해당하는 마지막 노드를 리턴하게 된다.

나는 result의 첫번째 노드를 더미노드처럼 넣어놓고 그 뒤부터 노드들을 연결했기 때문에 return을 result.next(더미노드의 다음 노드)로 하였다.

이 풀이의 시간복잡도는 $O(n)$이며 공간복잡도는 $O(n)$이다.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode cursor = result;

        int ol = 0;
        while (l1 != null || l2 != null) {
            int val = ol;
            val += l1 != null ? l1.val : 0;
            val += l2 != null ? l2.val : 0;

            ol = val / 10;
            val %= 10;

            cursor.next = new ListNode(val);
            cursor = cursor.next;

            if (l1 != null) {
                l1 = l1.next;
            }

            if (l2 != null) {
                l2 = l2.next;
            }
        }

        if (ol != 0) {
            cursor.next = new ListNode(ol);
        }

        return result.next;
    }
}

메모리를 개선한 두번째 풀이

첫번째 풀이에서 실행시간은 좋게 나왔지만 메모리에 대한 부분이 미흡하게 나왔다. return해야하는 LinkedList는 무조건 만들어야하니 필수이며 각 노드에 들어갈 값과 올림을 관리해야하기 때문에 필요한 변수만 선언해서 사용했다고 생각했다.

이를 개선하기 위해 내가 작성했던 코드를 다시 살펴보았다. 보다보니 올림을 관리하는 ol 변수를 없앨 수 있었다. 처음에는 반복문의 시작부분에 int val = ol로 초기화하였다. val은 ol로 시작하고 l1.val, l2.val을 더한 값이 된다. ol은 다시 val / 10의 값이 된다. 그리고 val은 다시 ol이 된다.

[val = ol] → [val += l1.val + l2.val] → [ol = val / 10] → [val = ol] → ...

즉 반복문의 마지막에 ol의 값이 반복문 시작의 val이 되는 것이다. 따라서 ol 변수를 사용하지 않더라도 val /= 10으로 같은 효과를 낼 수 있었다. ol 변수를 없애 개선한 코드는 다음과 같다.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode cursor = result;

        int val = 0;
        while (l1 != null || l2 != null) {
            val += l1 != null ? l1.val : 0;
            val += l2 != null ? l2.val : 0;

            cursor.next = new ListNode(val % 10);
            val /= 10;

            cursor = cursor.next;

            if (l1 != null) {
                l1 = l1.next;
            }

            if (l2 != null) {
                l2 = l2.next;
            }
        }

        if (val != 0) {
            cursor.next = new ListNode(val);
        }

        return result.next;
    }
}

결과는 약 0.7MB를 줄일 수 있었다.

이 이상으로 개선할 수 있는 방법을 찾지 못해 Solution을 참고했지만 대부분의 Solution들이 같은 방법으로 풀이하였다.