136일 (445. Add Two Numbers II) LinkedList

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

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

 

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.

 

Follow up: Could you solve it without reversing the input lists?

 

 

 

- 접근방법

* Stack을 이용하면 일의자리에 해당하는 연결리스트의 마지막 노드부터 ~ 가장 높은 자릿수인 첫번째 노드까지 값을 출력가능하다. (덧셈을 하기 위해 두 연결리스트의 자릿수를 통일해야하기 때문에 stack을 사용한다.)

 

1. 각 연결리스트의 값을 각 스택에 추가한다.

→ 스택은 마지막에  입력된 값부터 출력하기 때문에 두 연결리스트의 길이가 달라도 두 리스트 모두 일의 자릿수부터 출력하기 때문

 

2. 두 스택에 쌓인 값을 동시에 출력한다.

최초로 출력된 sum = stack1.pop() + stack2.pop()은 두 연결리스트의 일의 자릿수 합이 되겠다.

sum이 10이 넘는다면 다음 자릿수에 더할 carry의 값을 1 증가시키고, sum을 10으로 나눈 나머지가 현재 자릿수의 sum이 된다.

 

3. 하지만 스택에서 출력되는 값은 원하는 값의 정반대로 나온다.

스택은 후입선출이기 때문에 [1,2,3,4]를 얻고자하는데 [4,3,2,1]이 나온다.

따라서 원하는 값을 얻기위해 리스트의 링크를 스왑한다.

 

- 코드

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        ListNode head = new ListNode();
        ListNode answer = head;
        int carry = 0;

        while(l1 != null || l2 != null) { // 1
            if(l1 != null) {
                stack1.push(l1.val);
                l1 = l1.next;
            }
            if(l2 != null) {
                stack2.push(l2.val);
                l2 = l2.next;
            }
        }

        while(!(stack1.isEmpty() && stack2.isEmpty() && carry == 0)) { // 2
            int sum = 0;

            if(!stack1.isEmpty()) sum += stack1.pop();
            if(!stack2.isEmpty()) sum += stack2.pop();

            if(carry > 0) {
                sum += carry;
                carry = 0;
            }

            if(sum >= 10) {
                sum %= 10;
                carry++;
            }

            if(head.next == null) {
                head.next = new ListNode(sum);
            } else { // 3
                ListNode tempNode = head.next;
                head.next = new ListNode(sum);
                head.next.next = tempNode;
            }
        }

        return answer.next;
    }
}

 

두 연결리스트를 덧셈처럼 더하기 위해서 자릿수를 통일시켜야하는데

연결리스트는 끝까지 순회하지않으면 길이를 알 수 없으므로 자릿수를 통일시키기 위한 다른 방법이 생각나지않아 스택을 사용하게 되었다.

 

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform