Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Add Two Numbers

Add Two Numbers

Master this topic with zero to advance depth.

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Visual Representation

(2 -> 4 -> 3) + (5 -> 6 -> 4) = 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
Medium

Examples

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Approach 1

Level I: Iterative (Elementary Math)

Intuition

Iterate through both lists, adding digits along with a carry. Create a new node for each digit of the sum.

⏱ O(max(N, M)) where N and M are lengths of the lists💾 O(max(N, M)) for the result list

Detailed Dry Run

l1=[2,4], l2=[5,6].

  1. 2+5=7, carry=0.
  2. 4+6=10, carry=1. Node 0.
  3. Final carry 1. Node 1. Result: 7->0->1.
java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Be careful with the final carry; don't forget to add a node for it if it's non-zero.

Approach 2

Level II: Recursive

Intuition

Treat the addition of two lists as a recursive operation: add the current nodes and carry, then recurse for the next nodes.

⏱ O(max(N, M))💾 O(max(N, M)) recursion stack

Detailed Dry Run

l1=[2,4], l2=[5,6].

  1. Add(2, 5, 0): val=7, next=Add(4, 6, 0).
  2. Add(4, 6, 0): val=0, next=Add(null, null, 1).
  3. Add(null, null, 1): val=1, next=null. Result: 7->0->1.
java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    return add(l1, l2, 0);
}
private ListNode add(ListNode l1, ListNode l2, int carry) {
    if (l1 == null && l2 == null && carry == 0) return null;
    int val = carry + (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0);
    ListNode res = new ListNode(val % 10);
    res.next = add(l1 != null ? l1.next : null, l2 != null ? l2.next : null, val / 10);
    return res;
}

⚠️ Common Pitfalls & Tips

Ensure the base case handles the final carry correctly.

Approach 3

Level III: Optimized Iterative (In-place Re-use)

Intuition

To optimize space, we can re-use the nodes of the longer list instead of creating new ones. However, this is only possible if modifying the input is allowed.

  1. Determine which list is longer (or just pick one).
  2. Add values and carry to the existing nodes.
  3. If the list ends while carry > 0, append a new node.
⏱ O(max(N, M))💾 O(1) extra space (excluding result)

Detailed Dry Run

l1=[2,4], l2=[5,6,7]. Re-use l2.

  1. l2[0] = (2+5)%10 = 7. carry=0.
  2. l2[1] = (4+6)%10 = 0. carry=1.
  3. l2[2] = (1+7)%10 = 8. carry=0. Return l2.
java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    dummy.next = l1;
    ListNode curr = dummy, p1 = l1, p2 = l2;
    int carry = 0;
    while (p1 != null || p2 != null || carry != 0) {
        int sum = carry + (p1 != null ? p1.val : 0) + (p2 != null ? p2.val : 0);
        carry = sum / 10;
        if (p1 != null) {
            p1.val = sum % 10;
            curr = p1; p1 = p1.next;
        } else {
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }
        if (p2 != null) p2 = p2.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Modifying input lists is generally discouraged unless specified, but it's a valid 'memory-constrained' strategy.

← Previous QuestionCopy List with Random Pointer
Next Question →Intersection of Two Linked Lists