LeetCode 2 - Add Two Numbers

Add Two Numbers - LeetCode

두 연결리스트를 가지고 합을 계산해야 한다.

일종의 후위표기법이다. [2, 4, 3], [5, 6, 4] 이렇게 주어졌을 때 342 + 465 = 807이 되어 결과는 [7, 0, 8]이 정답이 된다.

길이가 다른 경우도 생각해 보자.

[2, 4, 3], [5, 7]이다. 이러면 342 + 75 = 417이 되고 [7, 1, 4]가 정답이 된다.

우선 자리 올림수(carry)가 발생한 경우를 생각해야 한다.

1. 두 연결리스트에서 값을 꺼낸다
2. 값을 더해 노드를 만든다.
3. 이때 캐리가 발생했다면 다음에 더하기 위해 기록해 둔다.
4. 캐리는 합을 10으로 나눈 몫이고 자릿수는 합을 10으로 나눈 나머지이다.
5. 반복이 끝났을 때 캐리가 남아있다면 추가해 준다.

/**
 * 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) {
        ListNode head = new ListNode();
        ListNode curr = head;
        int carry = 0;
        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;
            ListNode node = new ListNode(sum % 10);
            curr.next = node;
            curr = curr.next;
        }

        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return head.next;
    }
}