[LeetCode] 445. add Two Numbers 2 (해석, Java 풀이)

문제

https://leetcode.com/problems/add-two-numbers-ii/description/

주어진 두개의 비어있지 않은 linked list는 각각 음수가 아닌 정수로 이루어져있다. 가장 중요한 숫자가 첫번째로 오며, 그들의 노드 각각은 한자리 수를 포함한다. 두 숫자를 더한 합을 linked list 형태로 반환하라. 

두 숫자는 0일 경우를 제외하고, 앞자리가 0으로 나타나지 않는다.

 

풀이

Stack을 사용한 풀이

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ArrayDeque<Integer> st1 = new ArrayDeque<>();
    ArrayDeque<Integer> st2 = new ArrayDeque<>();

    while (l1 != null) {
        st1.push(l1.val);
        l1 = l1.next;
    }
    while (l2 != null) {
        st2.push(l2.val);
        l2 = l2.next;
    }

    ListNode result = null;
    int carry = 0;
    while (!st1.isEmpty() || !st2.isEmpty() || carry > 0) {
        int v1 = (!st1.isEmpty()) ? st1.pop() : 0;
        int v2 = (!st2.isEmpty()) ? st2.pop() : 0;

        int sum = v1 + v2 + carry;

        ListNode newNode = new ListNode(sum % 10);
        newNode.next = result;
        result = newNode;

        carry = sum / 10;
    }

    return result;
}

대체할 ArrayDeque를 스택 형태로 사용 - Stack 대신 ArrayDeque를 사용하는 이유 

또는 ListNode를 반대로 뒤집어, 동일하게 하나씩 더하는 방법도 있겠다.

 

시간 복잡도: O(max(n+m)), 공간 복잡도: O(n+m)

https://github.com/jeongum/java-algorithm/blob/master/stack/LeetCode_445_AddTwoNumbers.java