Leetcode - 2. Add Two Sum

Add Two Numbers - LeetCode

---

문제

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

---

양의 정수를 표현하는 링크드 리스트 두개가 있다. 둘을 더한 결과값을 표현하는 링크드 리스트를 리턴해라.

 

처음에 단순이 각각의 링크드 리스트를 숫자로 만들어 더해준 뒤 다시 그 숫자로 링크드 리스트를 만들려고 했다.

 

그러자 Int 였던 val 값이 표현가능한 값을 넘어가 버려서 런타임 에러가 났다.

 

아아 그렇다.. 자릿수끼리 더하면서 링크드 리스트를 만들어야 했던 것이다.

 

눈물과 함께 코드를 초기화 하고

 

각각의 자릿수를 더한 sum 값을 바탕으로 링크드 리스트에 노드를 추가했다.

 

/**
 * 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 sum = 0;
        ListNode root = new ListNode(-1);
        ListNode curr = root;
        while(l1 != null || l2 != null || sum >= 10) {
            sum =  sum / 10;
            if(l1 != null) {
                sum = sum + l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                sum = sum + l2.val;
                l2 = l2.next;
            }
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }
        return root.next;    
    }
}

 

1. root는 -1값으로 미리 만들어 준다.
2. 현재 노드를 나타내는 curr 도 만들어 준다.
3. l1 과 l2 가 null이 되고 sum이 10보다 작을 때 까지(carry가 없을 때 까지) while문을 반복한다.
4. sum = sum / 10 으로 sum을 carry 값으로 바꿔준다. 
5. l1과 l2 에서 Null 이 아닐때 각각의 값을 sum에 더해준다.
6. 현재 노드의 다음 노드의 val 에는 캐리를 뺀 한자릿 수 sum%10로 정해준다.
7. 그리고 현재 노드를 다음 위치로 옯겨준다.
8. 마지막 리턴에서는 root의 값을 -1로 먼저 넣어줬기 때문에 그 다음 노드를 리턴해준다.

[single linkedList 참고]