Add Two Numbers | Linked List Addition | Linked List

Overview

Add two numbers represented as linked lists: each list has digits in reverse order (least significant digit at head), and you return a new list representing the sum in the same format. You simulate digit-by-digit addition with a carry, building the result list from the dummy-head append pattern. This is a classic problem that combines list traversal with arithmetic and Dummy Head for building the result.

Key idea: Add digits at the same position (both heads, then both next, etc.), add the carry from the previous step, append (sum % 10) to the result, and set carry = sum / 10. When both lists and carry are exhausted, stop.

When to Use

Add two numbers as lists — Reverse order (LeetCode-style).
Add two numbers in forward order — Reverse both (or traverse to end), add, then reverse the result.
Multiply or other arithmetic on list-represented numbers — Same carry-based approach.

How It Works

Use a dummy head and a tail pointer for the result list.
Initialize carry = 0.
While l1 is not null, or l2 is not null, or carry is not 0:

Sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry.
Append a new node with value sum % 10 to tail; tail = new node.
carry = Math.floor(sum / 10).
Advance l1 and l2 if non-null.

Return dummy.next.

Example 1: Add Two Numbers (Reverse Order)

Problem: Two non-empty linked lists represent non-negative integers; digits stored in reverse order (head = ones place). Return the sum as a new list in reverse order.

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(-1);
  let tail = dummy;
  let carry = 0;
  while (l1 !== null || l2 !== null || carry !== 0) {
    const a = l1?.val ?? 0;
    const b = l2?.val ?? 0;
    const sum = a + b + carry;
    tail.next = new ListNode(sum % 10);
    tail = tail.next;
    carry = Math.floor(sum / 10);
    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }
  return dummy.next;
}

Time: O(n + m), Space: O(max(n,m)) for the result list (or O(1) extra if we don't count output).

Example 2: Handle Different Lengths and Final Carry

When one list is longer, the loop continues with 0 for the exhausted list. When both are exhausted but carry is 1 (e.g. 9+9=18), one more iteration appends the carry digit. The code above handles all cases with "l1 || l2 || carry".

Example 3: Add Two Numbers II (Forward Order)

Problem: Digits in forward order (head = most significant).

Approach: Reverse both lists, run the same add-two-numbers logic, then reverse the result. Or: push digits onto stacks, pop and add, build result in reverse.

Edge Cases

Different lengths — Use 0 when a list has no more digits.
Final carry — e.g. 5+5 = 10; one more node with value 1.
Both lists empty — With "carry !== 0" in the loop you'd still run once if carry were 1; if both empty and carry 0, return dummy.next (null). Usually problem says non-empty.
Leading zeros — Result list should not have leading zeros; normal construction doesn't add them.

Common Mistakes

Forgetting final carry — Loop condition must include carry so you output one more digit when carry is 1.
Wrong order of operations — Advance l1/l2 after reading their values and after appending the digit.
Creating a cycle — Ensure tail.next is set only to a new node and you advance tail; don't link back to l1/l2.

Time and Space Complexity

Time: O(n + m).
Space: O(max(n,m) + 1) for the result list; O(1) extra besides the result.

Summary

Add two numbers (reverse order): dummy + tail, carry; while l1 or l2 or carry: sum = a+b+carry, append sum%10, carry = sum/10; return dummy.next.
Same pattern for Add Two Numbers II (forward order: reverse, add, reverse result) and other list arithmetic.

See Dummy Head for building the result list and Merge Two Sorted for the two-list traversal pattern.

Add Two Numbers (List Representation)