☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Add two numbers as LinkedList

Medium TUF ID 2848 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given two non-empty linked lists, l1 and l2, each representing a non-negative integer. The digits are stored in reverse order: the head holds the units digit, the next node the tens digit, and so on. Every node holds a single digit 0..9, and there are no leading zeros except for the number 0 itself. Return the sum of the two numbers as a linked list in the same reversed format.

Constraints: each list has 1 to 100 nodes. That means the numbers can have up to 100 digits, far beyond what long (about 19 digits) can hold. The Java solutions also return an empty list when both inputs are empty.

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

Example 1

l1 = 2 -> 4 -> 3                 // the number 342
l2 = 5 -> 6 -> 4                 // the number 465
answer = 7 -> 0 -> 8             // 342 + 465 = 807

Example 2

l1 = 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9      // 9999999
l2 = 9 -> 9 -> 9 -> 9                     // 9999
answer = 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1   // 10009998, one digit longer than either input

A tempting trap. The obvious idea is to read each list into a long, add, and write the digits back out. It passes small tests and then fails on the first input with 20 or more digits, because the number silently overflows. The constraint of 100 digits rules it out. The approaches below never build the whole number; they add one digit column at a time, exactly as you would on paper.

The reversed order is what makes this pleasant. Column addition starts at the units digit and moves left, carrying into the next column. Here the units digits are at the heads, so walking the lists from the front visits the columns in exactly the order addition needs.

Approach 1: Brute force, copy the digits into arrays

Intuition. If linked lists feel awkward, move the data somewhere comfortable first. Copy each list’s digits into an array list (index i holds the digit of 10^i), then perform schoolbook addition on the arrays: for each column add the two digits and the incoming carry, keep sum % 10 and carry sum / 10 forward. A column sum is at most 9 + 9 + 1 = 19, so the carry is always 0 or 1. The result has at most max(m, n) + 1 digits, so an array of that size is enough. Finally, build the answer list from the result array.

Algorithm.

  1. Copy the digits of l1 into a and of l2 into b.
  2. Let len = max(|a|, |b|) and allocate sum of size len + 1.
  3. For i from 0 to len - 1: d = carry + a[i] + b[i] (treating missing digits as 0), store d % 10, set carry = d / 10.
  4. Put the final carry in sum[len], and include that slot only if the carry is non-zero.
  5. Build a list from sum and return it.
static ListNode bruteForce(ListNode l1, ListNode l2) {
    List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
    for (ListNode t = l1; t != null; t = t.next) a.add(t.val);
    for (ListNode t = l2; t != null; t = t.next) b.add(t.val);
    int len = Math.max(a.size(), b.size());
    int[] sum = new int[len + 1];                // one extra slot for a final carry
    int carry = 0;
    for (int i = 0; i < len; i++) {
        int d = carry + (i < a.size() ? a.get(i) : 0) + (i < b.size() ? b.get(i) : 0);
        sum[i] = d % 10;
        carry = d / 10;
    }
    sum[len] = carry;
    int used = carry > 0 ? len + 1 : len;
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int i = 0; i < used; i++) {
        tail.next = new ListNode(sum[i]);
        tail = tail.next;
    }
    return dummy.next;
}

Complexity. Time O(m + n): each digit is copied once and added once. Space O(m + n) extra for the two copies and the result array, in addition to the output list.

The method is correct, but the arrays are pure overhead: the lists already present the digits in the right order, so we can add while walking them.

Approach 2: Optimal, add while walking both lists

Intuition. Walk l1 and l2 side by side. At each step, add the current digit of each list (or 0 if that list has ended) to the carry, append a new node with sum % 10, and keep sum / 10 as the carry for the next column. A dummy node in front of the result means every new node is appended the same way, without a special case for the first one.

The loop condition l1 != null || l2 != null || carry != 0 packs in all three ways the sum can still have digits left: either list has unread digits, or there is a carry that has to become a final node. That last part is what produces the extra leading 1 in 5 + 5 = 10.

Why it is correct: after processing columns 0..k-1, the result list holds exactly the k lowest digits of the true sum and carry holds the amount flowing into column k. Each iteration preserves this, by the definition of column addition. When the loop ends, no digits and no carry remain, so the result holds every digit of the sum.

Algorithm.

  1. Create dummy, set tail = dummy and carry = 0.
  2. While l1 or l2 is non-empty, or carry != 0:
    • sum = carry, plus l1.val if l1 exists (then advance l1), plus l2.val if l2 exists (then advance l2).
    • Append a node with sum % 10 and move tail to it.
    • Set carry = sum / 10.
  3. Return dummy.next.
static ListNode optimal(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), tail = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {   // a leftover carry still needs a node
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
        carry = sum / 10;
    }
    return dummy.next;
}

Dry run on Example 1:

column l1 digit l2 digit carry in sum digit written carry out
0 2 5 0 7 7 0
1 4 6 0 10 0 1
2 3 4 1 8 8 0

Both lists are now exhausted and the carry is 0, so the loop stops with 7 -> 0 -> 8.

Complexity. Time O(max(m, n)): one iteration per column, plus at most one more for a final carry. Space O(1) extra apart from the output. The output itself has max(m, n) + 1 nodes at most, which any solution has to create.

Edge cases and pitfalls