[LeetCode/Medium] 2. Add Two Numbers

1. Input

1) ListNode l1

- 첫 번째 숫자를 일의자리부터 거꾸로 나타낸 ListNode

2) ListNode l2

- 두 번째 숫자를 일의자리부터 거꾸로 나타낸 ListNode

 

2. Output

1) 첫 번째 숫자와 두 번째 숫자의 합을 일의자리부터 거꾸로 나타낸 ListNode를 반환

 

3. Constraint

1) 각 linked list의 노드 수의 범위는 [1, 100]이다.

2) 0 <= Node.val <= 9

3) 합하는 두 수 모두 선행 0(0000078과 같이 앞 부분에 자리만 차지하는 0)은 없다.

 

4. Example

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

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

설명:

- 342 + 465 = 807

- 9,999,999 + 9,999 = 10,009,998

 

5. Code

/**
 * 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) {   
        int carry = 0;
        Queue<Integer> q = new LinkedList<>();
        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;
            q.add(sum%10);
        }
        if(carry==1) q.add(1);
        ListNode ans = new ListNode(q.remove());
        ListNode cur = ans;
        while(!q.isEmpty()){
            ListNode n = new ListNode(q.remove());
            cur.next = n;
            cur = cur.next;
        }
        return ans;
    }
}

- 99%, 6%