☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Add two numbers in Linked List

Medium TUF ID 625 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Two non-negative integers are given as singly linked lists, one decimal digit per node, with the digits stored in reverse order: the head holds the units digit. Add the two numbers and return the sum as a linked list in the same reversed format. Neither number has leading zeros, except for the number 0 itself, which is the single node 0.

Constraints: each list has 1 ≤ n ≤ 100 nodes (the approaches below work for any length), each digit is 0..9. The lists can be of different lengths.

Example 1

l1 = 2 -> 4 -> 3        // 342
l2 = 5 -> 6 -> 4        // 465
answer = 7 -> 0 -> 8    // 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

Example 3

l1 = 0, l2 = 0
answer = 0

Storing the digits in reverse order is deliberate: it makes the units digit the first node, so the carry flows in the same direction as the next pointers.

Approach 1: Brute force, convert to numbers

Intuition. The most literal approach is to turn each list into an integer, add the integers, and write the digits of the sum back into a list. Reading a reversed-digit list into a number is easy: the first node is multiplied by 1, the second by 10, the third by 100, and so on.

Algorithm.

  1. Convert l1 and l2 to long with toLong, multiplying each digit by an increasing power of ten.
  2. Add the two values.
  3. If the sum is 0, return a single node 0.
  4. Otherwise peel digits off the sum with % 10 and / 10, appending each to a new list behind a dummy head.
static ListNode bruteForce(ListNode l1, ListNode l2) {
    long sum = toLong(l1) + toLong(l2);
    if (sum == 0) return new ListNode(0);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (sum > 0) {
        tail.next = new ListNode((int) (sum % 10));
        tail = tail.next;
        sum /= 10;
    }
    return dummy.next;
}

static long toLong(ListNode head) {
    long value = 0, place = 1;
    int digits = 0;
    for (ListNode t = head; t != null; t = t.next) {
        if (++digits > 18) throw new IllegalArgumentException("more than 18 digits: does not fit in a long");
        value += t.val * place;
        place *= 10;
    }
    return value;
}

Complexity. Time O(n + m) to read the lists and O(max(n, m)) to write the result. Space O(1) apart from the output list.

Why this is not acceptable. A long holds at most 18 full decimal digits. The linked-list representation exists precisely so numbers can be arbitrarily long, and a 19-digit input silently overflows into garbage. toLong throws instead of returning a wrong answer, and the test file checks that it does on a 25-digit input. BigInteger would avoid the overflow, but it is heavier than the problem deserves, and it would hide the digit-level reasoning that the interviewer wants to see.

Approach 2: Better, digit-by-digit with a carry into a new list

Intuition. Do what the brute force does, but never materialise the whole number. Walk both lists in lockstep. At each position the result digit is (a + b + carry) % 10 and the new carry is (a + b + carry) / 10. When one list runs out, treat its missing digits as 0. When both lists are exhausted and the carry is still 1, that carry is one more digit. A dummy head makes appending to the result uniform.

Algorithm.

  1. Create a dummy node and a tail pointer at it; set carry = 0.
  2. While l1 or l2 still has a node, or carry is non-zero:
    • sum = carry, plus l1.val if l1 exists (then advance l1), plus l2.val if l2 exists (then advance l2).
    • Append a node holding sum % 10; set carry = sum / 10.
  3. Return dummy.next.
static ListNode better(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), 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; }
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
        carry = sum / 10;
    }
    return dummy.next;
}

Complexity. Time O(max(n, m)): one step per result digit, and the result has at most max(n, m) + 1 digits. Space O(max(n, m)) for the newly built answer, O(1) otherwise.

The loop condition || carry != 0 is the detail most people forget: it is what turns 5 + 5 into 0 -> 1 instead of just 0. Since each digit is at most 9, sum ≤ 9 + 9 + 1 = 19, so the carry is always 0 or 1 and the extra iteration happens at most once.

Why “better” rather than “optimal”? This version is the one to write in an interview: it is short, obviously correct, and leaves the inputs untouched. Its only cost is that it allocates a brand-new node for every digit of the result.

Approach 3: Optimal, reuse the nodes of the inputs

Intuition. The answer has the same length as the longer input, plus possibly one node. So instead of allocating a fresh list, we can overwrite the digits of l1 in place and, when l2 is longer, splice l2’s leftover tail onto the result. At most one new node is ever created, for a final carry.

Algorithm.

  1. If either list is empty, the other list is the answer.
  2. Remember head = l1. Walk while both lists have nodes: write (l1.val + l2.val + carry) % 10 into l1, update the carry, remember prev = l1, advance both.
  3. If l1 ran out first, attach the remainder of l2 after prev and continue on it (l1 = l2).
  4. While nodes remain and the carry is non-zero, add the carry into the current node and advance.
  5. If the carry is still non-zero after the last node, append one new node holding it.
  6. Return head.
static ListNode optimal(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    ListNode head = l1, prev = null;
    int carry = 0;
    while (l1 != null && l2 != null) {                // digits present in both numbers
        int sum = l1.val + l2.val + carry;
        l1.val = sum % 10;
        carry = sum / 10;
        prev = l1;
        l1 = l1.next;
        l2 = l2.next;
    }
    if (l1 == null) {                                 // l2 is longer: continue on l2's remaining nodes
        prev.next = l2;
        l1 = l2;
    }
    while (l1 != null && carry != 0) {                // push the carry through the remaining digits
        int sum = l1.val + carry;
        l1.val = sum % 10;
        carry = sum / 10;
        prev = l1;
        l1 = l1.next;
    }
    if (carry != 0) prev.next = new ListNode(carry);  // ran out of digits with a carry left: one new node
    return head;
}

Dry run on l1 = 9 -> 9, l2 = 1:

phase l1.val l2.val carry in written carry out
both lists 9 1 0 0 1
l2 exhausted, l1 continues 9 - 1 0 1
no nodes left, carry 1 - - 1 new node 1 0

Result: 0 -> 0 -> 1, which is 99 + 1 = 100.

Complexity. Time O(max(n, m)), the same as Approach 2. Space O(1) extra: the result reuses existing nodes and allocates at most one.

The second loop stops as soon as the carry is 0. Any digits after that point belong to the longer input and are already correct, and since prev.next still points at them, they remain part of the result without being visited.

The price of this approach is that it destroys l1 (and borrows l2’s tail). That is fine when the inputs are throwaway, and it is the version to mention when an interviewer asks for O(1) extra space.

Edge cases and pitfalls