Add Two Numbers

NeetCode: Add Two Numbers · LeetCode: 2. Add Two Numbers · Difficulty: Medium

Two non-empty linked lists hold non-negative integers with digits in reverse order (the head is the ones digit). Add them and return the sum in the same format.

Example

Text

Input:  (1 -> 2 -> 3) + (4 -> 5 -> 6)    Output: 5 -> 7 -> 9      (321 + 654 = 975)
Input:  (9 -> 9)      + (1)              Output: 0 -> 0 -> 1      (99 + 1 = 100)

Each node is a ListNode object with an int val and a next reference. A next of null marks the end of the list. The list is built from mutable fields and null, with no wrapper types. The helper fromArray builds a list from digits, and toList reads a list back into a List<Integer> so it can be printed.

Brute force: convert to integers

Read each list as a number, add, and write the sum back out digit by digit. Each list is read into a long, which holds every number of up to 18 digits.

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    private long toNumber(ListNode list) {
        List<Integer> digits = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            digits.add(node.val);
        }
        long number = 0;
        for (int i = digits.size() - 1; i >= 0; i--) {
            number = number * 10 + digits.get(i);
        }
        return number;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        long sum = toNumber(l1) + toNumber(l2);
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        do {
            tail.next = new ListNode((int) (sum % 10));
            tail = tail.next;
            sum /= 10;
        } while (sum > 0);
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... digits) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int d : digits) {
            tail.next = new ListNode(d);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            out.add(node.val);
        }
        return out;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(toList(solution.addTwoNumbers(fromArray(1, 2, 3), fromArray(4, 5, 6))));
        System.out.println(toList(solution.addTwoNumbers(fromArray(9, 9), fromArray(1))));
    }
}

Output

[5, 7, 9]
[0, 0, 1]

Time: O(n). Space: O(n). It only works while each number fits in a long (at most 18 digits each is safe, since the sum of two 18-digit numbers is below Long.MAX_VALUE). The problem allows lists of up to 100 digits, and a long that overflows wraps around silently, so this approach returns wrong answers on large inputs.

Optimal: add digit by digit with a carry

The lists are already stored ones-digit first, the order used in column addition by hand. Walk both lists together, add the two digits plus the carry, output sum % 10, and carry sum / 10. Keep going while either list has digits or a carry is left. A dummy head node avoids a special case for the first output node.

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            carry = sum / 10;
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... digits) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int d : digits) {
            tail.next = new ListNode(d);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            out.add(node.val);
        }
        return out;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(toList(solution.addTwoNumbers(fromArray(1, 2, 3), fromArray(4, 5, 6))));
        System.out.println(toList(solution.addTwoNumbers(fromArray(9, 9), fromArray(1))));
        System.out.println(toList(solution.addTwoNumbers(fromArray(0), fromArray(0))));
    }
}

Output

[5, 7, 9]
[0, 0, 1]
[0]

Time: O(max(m, n)). Space: O(max(m, n)) for the result. There is no length limit. The method moves the parameters l1 and l2 forward, which changes only the local references, not the caller's lists.