[Java] LeetCode 2번 Add Two Numbers

총 3단계로 풀이가 진행되었다. l1과 l2의 길이가 다르고, 최대 100개까지 이어질 수 있다.

1. l1과 l2의 공통 조상을 먼저 더하여 노드로 만들어준다.

2. 공통조상을 제외하고 남은 l1또는 l2를 더해준다.

3. 마지막에 올림이 남았으면 노드를 추가해준다.

컴퓨터 구조에서 가산기를 구현하는 것과 비슷한다. carry라는 변수에 올림이 발생했는지를 저장하고 이것을 더할 때마다 계속 사용했다. 그리고 마지막에도 올림이 발생하였으면 최고 자리수가 1이 되도록 만드는 것이 포인트이다.

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;
        ListNode answer = null;
        ListNode curNode = null;
        while (true) {
            if (l1 != null && l2 != null) {
                int num = l1.val + l2.val + carry;
                if (num >= 10) {
                    carry = 1;
                } else {
                    carry = 0;
                }
                num %= 10;
                ListNode newNode = new ListNode(num);
                if (answer == null) {
                    answer = newNode;
                    curNode = answer;
                } else {
                    curNode.next = newNode;
                    curNode = newNode;
                }
                l1 = l1.next;
                l2 = l2.next;
            } else {
                break;
            }
        }
        while (l1 != null) {
            int num = l1.val + carry;
            if (num >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            num %= 10;
            ListNode newNode = new ListNode(num);
            curNode.next = newNode;
            curNode = newNode;
            l1 = l1.next;
        }
        while (l2 != null) {
            int num = l2.val + carry;
            if (num >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            num %= 10;
            ListNode newNode = new ListNode(num);
            curNode.next = newNode;
            curNode = newNode;
            l2 = l2.next;
        }
        if (carry == 1) {
            curNode.next = new ListNode(1);
        }
        return answer;
    }
}