Add Two Numbers

Medium Linked List Dummy Node Pattern Original on LeetCode

Add Two Numbers is a medium linked list problem solved with the dummy node pattern pattern. The best approach, optimal (one pass with a dummy head), runs in O(max(m, n)) time and O(1) extra space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy digits into arrays) up.

Problem

You are given two non-empty linked lists l1 and l2, each representing a non-negative whole number. The digits are stored in reverse order: the first node holds the ones digit, the next node the tens digit, and so on. Every node holds a single digit.

Return the sum of the two numbers as a linked list in the same reverse-digit format.

Examples

Example 1

Input
l1 = [4, 6, 2], l2 = [7, 5]
Output
[1, 2, 3]
Why
The lists hold 264 and 57 with the ones digit first; 264 + 57 = 321, stored as [1, 2, 3].

Example 2

Input
l1 = [8, 9, 9], l2 = [3]
Output
[1, 0, 0, 1]
Why
998 + 3 = 1001: the carry ripples through every digit and adds a new node at the end.

Example 3

Input
l1 = [0], l2 = [5, 1]
Output
[5, 1]
Why
0 + 15 = 15.

Constraints

  • Each list has between 1 and 100 nodes.
  • 0 <= Node.val <= 9
  • Neither number has leading zeros, except the number 0 itself (the single node [0]).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (copy digits into arrays)O(m + n)O(m + n)
Optimal (one pass with a dummy head)O(max(m, n))O(1) extra

1Brute force (copy digits into arrays)

TimeO(m + n)Each list is read once and each result digit is produced once.
SpaceO(m + n)The two digit arrays and the result array are extra copies of the input.

Read both lists into digit arrays, add the arrays position by position with a carry like on paper, and then build a new list from the resulting digits. Converting to a built-in integer is not an option, because a number can have 100 digits.

  1. Copy the digits of l1 into array a and those of l2 into array b (ones digit first).
  2. For i from 0 to max(len(a), len(b)) - 1, add a[i] + b[i] + carry (missing digits count as 0); store sum % 10 and keep sum / 10 as the carry.
  3. If a carry remains, append it as one more digit.
  4. Build a new linked list from the result digits and return it.
class Solution {
    private List<Integer> digits(ListNode node) {
        List<Integer> d = new ArrayList<>();
        for (; node != null; node = node.next) d.add(node.val);
        return d;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        List<Integer> a = digits(l1), b = digits(l2);
        List<Integer> sum = new ArrayList<>();
        int carry = 0;
        for (int i = 0; i < Math.max(a.size(), b.size()); i++) {
            int s = carry;
            if (i < a.size()) s += a.get(i);
            if (i < b.size()) s += b.get(i);
            sum.add(s % 10);
            carry = s / 10;
        }
        if (carry > 0) sum.add(carry);
        ListNode head = null;
        for (int i = sum.size() - 1; i >= 0; i--) head = new ListNode(sum.get(i), head);
        return head;
    }
}

2Optimal (one pass with a dummy head)

TimeO(max(m, n))One step per digit of the longer list, plus at most one step for a final carry.
SpaceO(1) extraOnly a few pointers and the carry; the output list itself is the required answer.

Walk both lists at the same time and build the answer as you go. At each step add the two current digits (0 for a list that has ended) and the carry, append a node with the ones digit of that sum, and carry the rest. A dummy node in front of the answer means appending always looks the same.

  1. dummy = new node, tail = dummy, carry = 0.
  2. While l1 or l2 is not null or carry > 0: s = carry + (l1's digit or 0) + (l2's digit or 0).
  3. Append a node with s % 10 after tail, move tail to it, set carry = s / 10, and advance l1 and l2 if they are not null.
  4. Return dummy.next.
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), tail = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int s = carry;
            if (l1 != null) { s += l1.val; l1 = l1.next; }
            if (l2 != null) { s += l2.val; l2 = l2.next; }
            tail.next = new ListNode(s % 10);
            tail = tail.next;
            carry = s / 10;
        }
        return dummy.next;
    }
}

Edge cases to test

  • Lists of very different lengths: the shorter one runs out first
  • A carry left over after both lists end needs one extra node
  • Both numbers are 0
  • Up to 100 digits: far too big to convert to an int or long

Hints

Hint 1

The ones digits come first, which is exactly the order you add numbers by hand.

Hint 2

Add the two current digits plus a carry; the new digit is the sum mod 10 and the next carry is the sum divided by 10.

Hint 3

Keep going while either list still has nodes or the carry is not zero, treating a finished list as digit 0. A dummy head node avoids special-casing the first node.

FAQ

What is the best time complexity for Add Two Numbers?

Optimal (one pass with a dummy head) runs in O(max(m, n)) time and O(1) extra extra space. One step per digit of the longer list, plus at most one step for a final carry.

Which pattern does Add Two Numbers use?

It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Remove Linked List Elements, Delete Nodes From Linked List Present in Array, Merge Two Sorted Lists.

Is there a brute force solution for Add Two Numbers?

Yes. Brute force (copy digits into arrays) takes O(m + n) time and O(m + n) space. Read both lists into digit arrays, add the arrays position by position with a carry like on paper, and then build a new list from the resulting digits.

Which edge cases should I test for Add Two Numbers?

Lists of very different lengths: the shorter one runs out first; A carry left over after both lists end needs one extra node; Both numbers are 0; Up to 100 digits: far too big to convert to an int or long.