[LeetCode] #2. Add Two Numbers(Medium)

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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

해석)

두 개의 음이 아닌 정수를 나타내는 두 개의 non-empty linked-list가 주어진다. 숫자는 역순으로 저장되어 있으며, 각 노드에는 한 자리 숫자만 포함된다. 두 숫자를 추가하고 합계를 linked-list로 반환하시오.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Input: l1 = [0], l2 = [0]
Output: [0]

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

ListNode는 아래와 같이 주어진다. 아래를 이용해서 구하면 된다.

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; }
}

풀이 1번

오랜만에 해서 그냥 무식하게 만들었는데, 설명하면 다음과 같다.

l1과 l2이 둘다 null이 아닐 경우
- sum과 add를 add + l1.val + l2.val을 각각 %와 / 연산을 통해 값을 구한다.
- 그러고 create함수를 통해 ListNode를 생성하는데 생성시 root의 맨 끝까지 이동 후 값을 넣는다.
l1과 l2 중 하나라도 null이 나올 경우
- l1 또는 l2의 값만 add 값과 더하여 node를 추가한다.
add가 남아있는 경우 add의 값을 추가해준다.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int add = 0;
        int sum = 0;
        ListNode answer = null;
        while (l1 != null && l2 != null) {
            sum = (add + l1.val + l2.val) % 10;
            add = (add + l1.val + l2.val) / 10;
            answer = create(answer, sum);
            l1 = l1.next;
            l2 = l2.next;
        }

        while (l1 != null) {
            sum = (add + l1.val) % 10;
            add = (add + l1.val) / 10;
            answer = create(answer, sum);
            l1 = l1.next;
        }

        while (l2 != null) {
            sum = (add + l2.val) % 10;
            add = (add + l2.val) / 10;
            answer = create(answer, sum);
            l2 = l2.next;
        }

        answer = add > 0 ? create(answer, add) : answer;
        
        return answer;
    }

    private ListNode create(ListNode root, int val){
        if(root == null){
            return new ListNode(val);
        }

        ListNode copy = root;
        while(copy.next != null){
            copy = copy.next;
        }
        copy.next = new ListNode(val);
        return root;
    }
}

풀이2번

1번을 풀고 코드를 다시보니 개선할게 많았다. dummy를 두고 dummy를 이동시킨 다음 해당 dummy에 node를 추가하는 방식으로 처리했다.

마지막에 new ListNode(1) 을 한 이유는 상식적으로 add(carry)가 2가 넘을 순 없다고 생각했기 때문이다.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int add = 0;
        int sum = 0;

        ListNode answer = new ListNode();
        ListNode dummy = answer;
        while (l1 != null || l2 != null) {
            int x = (l1 == null) ? 0 : l1.val;
            int y = (l2 == null) ? 0 : l2.val;
            sum = (add + x + y);
            add = sum / 10;
            dummy.next = new ListNode(sum % 10);
            dummy = dummy.next;
            l1 = (l1 == null) ? null : l1.next;
            l2 = (l2 == null) ? null : l2.next;
        }

        if(add > 0){
            dummy.next = new ListNode(1);
        }

        return answer.next;
    }

[LeetCode] 2. Add Two Numbers(Medium)

[LeetCode] #2. Add Two Numbers(Medium)

풀이 1번

풀이2번

1o2o3o