[leetcode #2] Add Two Numbers

Problem

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.

Example 1:

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

Example 2:

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

Example 3:

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

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.

Idea

주어진 두 List의 값들을 각 수의 자리수라 생각하고 더한 결과를 List로 반환하라는 문제다.

덧셈이기 때문에 두 List를 탐색하면서 받아올림 (carry)이 생겼을 때 1을 다음 노드의 값에 더해주면 된다. 새로운 노드를 생성하면 쉽게 풀 수 있지만 메모리를 줄이기 위해 원래 있던 l1 List를 사용하기로 했다.

l1과 l2가 null이 아닐 때까지 두 노드의 수를 하나로 합쳐 l1에 저장한다. 받아올림이 생겼을 경우 받아올림을 다음 노드들의 합에 더한다.

l1과 l2 두 List 중 남은 List를 remained 포인터로 가리킨다. 이 때 마지막에 받아올림이 생길 가능성이 있으므로 remained의 뒷 포인터인 end 포인터도 만든다.

remained List를 탐색하면서 앞에서와 같은 방식으로 받아올림을 처리한다. 마지막에 받아올림이 남았으면 새로운 노드를 만들고 end 포인터가 가리키게 하면 된다.

Time Complexity: O(n)
Space Complexity: O(1)

Solution

/**
 * 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 rounded = 0;
        ListNode head = l1;
        ListNode end = l1;

        while (l1 != null && l2 != null) {
            int val = rounded + l1.val + l2.val;
            rounded = val >= 10 ? 1 : 0;
            l1.val = val % 10;

            end = l1;
            l1 = l1.next;
            l2 = l2.next;
        }

        ListNode remained = l1;
        if (l1 == null) {
            remained = l2;
        }
        end.next = remained;

        while (remained != null) {            
            int val = rounded + remained.val;
            rounded = val >= 10 ? 1 : 0;
            remained.val = val % 10;

            remained = remained.next;
            end = end.next;
        }

        if (rounded != 0) {
            end.next = new ListNode(1);
        }

        return head;
    }
}

Reference

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