Add Two Numbers - Linked List Walkthrough

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

Each linked list node stores one digit. Digits are stored in reverse order: the ones place appears first, then tens, hundreds, and so on.

Return a new linked list representing the sum, also in reverse order.

Examples

Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
342 + 465 = 807

Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints

1 <= list length <= 100
0 <= node.val <= 9
The number does not contain leading zeros except the number 0 itself

🎯 Real-World Analogy

Cash Register Tape Addition

Imagine you are adding two long receipts where each line is a digit column. You start from the smallest unit (cents), write the result digit, and carry any overflow to the next line.

A linked list here behaves like that receipt tape: one digit at a time, moving forward. You never need the full number materialized as one giant integer.

This is why a digit-by-digit traversal with a carry variable is the clean, scalable approach.

💡 Key Insights

Reverse order means the first node is the ones place, so left-to-right traversal works naturally.
At each step, sum = digit1 + digit2 + carry; next digit is sum % 10.
Carry for the next node is sum // 10.
Use a dummy head node to simplify list construction and return logic.
Continue while either list has nodes or carry is non-zero.

💻 Solution Approaches

Approach 1: Convert to Integers (Not Preferred)

Time: O(N + M) | Space: O(N + M)

Convert both linked lists to integers, add them, then rebuild a linked list. This is easy conceptually but can overflow in languages without arbitrary precision and adds conversion overhead.

Approach 2: In-Place Digit Addition (Recommended)

Time: O(max(N, M)) | Space: O(max(N, M)) for result list

Traverse both lists together, compute one digit at a time, and propagate carry forward.

Python Implementation

          class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def add_two_numbers(l1: ListNode, l2: ListNode) -> ListNode:
    """
    Add two numbers represented as reverse-order linked lists.

    Time: O(max(N, M))
    Space: O(max(N, M))
    """
    dummy = ListNode(0)
    tail = dummy
    carry = 0

    while l1 or l2 or carry:
        v1 = l1.val if l1 else 0
        v2 = l2.val if l2 else 0

        total = v1 + v2 + carry
        carry = total // 10
        digit = total % 10

        tail.next = ListNode(digit)
        tail = tail.next

        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next
        

JavaScript Implementation

          function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

function addTwoNumbers(l1, l2) {
  /**
   * Add two reverse-order linked-list numbers.
   *
   * Time: O(max(N, M))
   * Space: O(max(N, M))
   */
  const dummy = new ListNode(0);
  let tail = dummy;
  let carry = 0;

  while (l1 !== null || l2 !== null || carry > 0) {
    const v1 = l1 ? l1.val : 0;
    const v2 = l2 ? l2.val : 0;

    const total = v1 + v2 + carry;
    carry = Math.floor(total / 10);
    const digit = total % 10;

    tail.next = new ListNode(digit);
    tail = tail.next;

    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }

  return dummy.next;
}
        

🔍 Step-by-Step Walkthrough

Trace l1 = [2,4,3] and l2 = [5,6,4]:

Start: carry = 0, result = []

            Step 1: 2 + 5 + 0 = 7

            digit = 7, carry = 0

            result = [7]
          
            Step 2: 4 + 6 + 0 = 10

            digit = 0, carry = 1

            result = [7, 0]
          
            Step 3: 3 + 4 + 1 = 8

            digit = 8, carry = 0

            result = [7, 0, 8]
          
Final: [7, 0, 8]

⚡ Complexity Analysis

Time Complexity: O(max(N, M))

Each node from both lists is visited at most once.
Per iteration work is constant: read values, add, split digit/carry, append node.
Total runtime follows the longer input list.

Space Complexity: O(max(N, M))

A new result list is created and can be as long as the longer input plus one carry node.
Auxiliary variables (carry, pointers) are O(1).

Trade-off vs Integer Conversion

Approach	Time	Space	Risk
Convert to integers	O(N + M)	O(N + M)	Potential overflow / conversion complexity
Digit-by-digit linked list addition	O(max(N, M))	O(max(N, M))	None; directly matches data structure

🔧 Edge Cases

One list much longer than the other (carry must continue correctly).
Final carry creates a new node (e.g., 9 + 1 -> 0 -> 1).
Both lists are single zero node.
Repeated carry chain (e.g., 9999 + 1).

🧪 Test Cases

Case 1
[2,4,3] + [5,6,4] -> [7,0,8]

Case 2
[9,9,9] + [1] -> [0,0,0,1]

Case 3
[0] + [0] -> [0]

💼 Interview Tips

What interviewers probe:

Can you reason about carry flow without converting to integers?
Do you handle different list lengths cleanly?
Do you explain why a dummy head simplifies implementation?
Can you discuss follow-up: digits in forward order?

🎓 Key Takeaways

Use carry as first-class state while traversing linked lists.
Dummy head eliminates special-case handling for result list start.
Stop condition must include pending carry.
This pattern generalizes to many linked-list arithmetic problems.

← Back to All Algorithms