[LeetCode] Add Two Numbers

문제

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

알고리즘

Linked List

풀이

쉬운 문제였는데 이해를 못해서 어렵다고 느낀 거 같다.

1. 두 개의 노드를 뒤집고 자릿수 별로 더해서 다시 뒤집은 노드를 반환해야 한다.
2. 결국 두 개의 노드를 순서대로 자릿수 별로 더해서 해당 노드를 반환하면 된다.
3. 대신 자릿수를 더할 때 10 이상이면 다음 자리에 1을 반환해야 한다.
4. 마지막 자릿수가 10 이상인 경우에는 자릿수를 하나 더 추가해서 1을 넣어주어야 한다.
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 listNode = new ListNode(0);
        ListNode result = listNode;
        int carry = 0;

        while (l1 != null || l2 != null) {

			// 이전 while문에서 carry 값이 넘어오면 sum에 먼저 더해준다.
            int sum = carry;

			// 첫번째 노드가 null이 아니면 sum에 더해준다.
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

			// 두번째 노드가 null이 아니면 sum에 더해준다.
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

			// sum 값이 10을 넘어가면 carry의 값을 1로 변경하고 sum-10을 다음 노드의 값으로 넣어준다.
            // 10을 넘지 않으면 그대로 다음 노드의 값으로 넣어준다.
            if (sum >= 10) {
                listNode.next = new ListNode(sum - 10);
                carry = 1;
            } else {
                listNode.next = new ListNode(sum);
                carry = 0;
            }

            listNode = listNode.next;
        }

		// 마지막 계산에서 carry 값이 있다면 다음 노드 하나를 더 추가해서 1을 넣어준다.
        if (carry == 1) {
            listNode.next = new ListNode(1);
        }

        return result.next;

    }
}