Add Two Numbers Represented as Linked Lists

Two non-empty linked lists represent two non-negative integers. The digits are stored in reverse order, one digit per node, so the head is the ones digit. Add the numbers and return the sum as a list in the same format.

LeetCode: 2. Add Two Numbers

Example

Text

Input:  (1 -> 8 -> 2) + (3 -> 6 -> 5)    Output: 4 -> 4 -> 8     (281 + 563 = 844)
Input:  (4 -> 8 -> 1) + (3 -> 6)         Output: 7 -> 4 -> 2     (184 + 63 = 247)

Brute force: convert to integers

Read each list into a number, add them, and write the sum back out digit by digit.

Java

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

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

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

    static long toNumber(ListNode list) {
        long number = 0, place = 1;
        for (ListNode node = list; node != null; node = node.next) {
            number += node.val * place;
            place *= 10; // wraps silently on overflow
        }
        return number;
    }

    static ListNode fromNumber(long n) {
        List<Integer> digits = new ArrayList<>();
        do {
            digits.add((int) (n % 10));
            n /= 10;
        } while (n != 0);
        ListNode head = null;
        for (int i = digits.size() - 1; i >= 0; i--) {
            head = new ListNode(digits.get(i), head);
        }
        return head;
    }

    static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return fromNumber(toNumber(l1) + toNumber(l2));
    }

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

Output

[4, 4, 8]
[7, 4, 2]

Time: O(m + n). Space: O(max(m, n)) for the result.

This only works while the numbers fit in a long, which holds 18 full digits. LeetCode's lists can have 100 digits, and place *= 10 overflows long before that. Java long arithmetic wraps silently, so the result would be wrong without any error.

Optimal: add digit by digit

Add the lists the way you add on paper: the ones digits first, then the tens, carrying 1 whenever a column reaches 10. The reversed order means the lists are already in the right order for that. Keep going while either list has digits or a carry is left over.

Java

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

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

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

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

    public static void main(String[] args) {
        System.out.println(toList(addTwoNumbers(fromArray(1, 8, 2), fromArray(3, 6, 5))));
        System.out.println(toList(addTwoNumbers(fromArray(4, 8, 1), fromArray(3, 6))));
        System.out.println(toList(addTwoNumbers(fromArray(9, 9, 9), fromArray(1))));
        int[] big = new int[30];
        Arrays.fill(big, 9);
        System.out.println(toList(addTwoNumbers(fromArray(big), fromArray(1))).size());
    }
}

Output

[4, 4, 8]
[7, 4, 2]
[0, 0, 0, 1]
31

Time: O(max(m, n)). Space: O(max(m, n)) for the result, O(1) besides it.

The loop only advances the parameters l1 and l2 and never changes a node, so the inputs stay intact and the result is a fresh list. List nodes use null for "no next node" and have mutable fields. A dummy node gives tail somewhere to start, which avoids a special case for the first digit.

Edge cases

Different lengths: a finished list contributes 0.
Final carry: 999 + 1 needs a new node for the leading 1.
Digits stored most significant first (LeetCode 445): reverse both lists, add, and reverse the result, or push the digits onto two stacks first.