Add Two Numbers

MediumLinked ListLinked ListMathRecursion

Problem

You are given two linked lists, each representing a non-negative integer with its digits stored in reverse order, the ones place first, one digit per node. Add the two numbers together and return the sum in the same reversed-digit list format.

Example. 2 -> 4 -> 3 represents 342, and 5 -> 6 -> 4 represents 465; their sum 807 is returned as 7 -> 0 -> 8.

Key idea

Storing digits least-significant-first is not an inconvenience here: it is exactly the order needed to add numbers the way arithmetic is normally done by hand, starting from the ones place and working outward, without ever needing to reverse either list first.

Walk both lists together, one node at a time. At each position, add the two current digits (treating an exhausted list as contributing zero) plus whatever carry came from the previous position. The digit to record is that sum modulo ten, and the carry to pass forward is that sum divided by ten. Keep going as long as either list still has nodes or a carry is still pending, since a carry alone can create one final extra digit after both inputs are exhausted.

Solution

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;
  let carry = 0;

  while (l1 !== null || l2 !== null || carry !== 0) { // a leftover carry can still add one more digit
    const digit1 = l1 !== null ? l1.val : 0;
    const digit2 = l2 !== null ? l2.val : 0;
    const sum = digit1 + digit2 + carry;

    carry = Math.floor(sum / 10); // carry forward to the next position
    tail.next = new ListNode(sum % 10); // ones digit of the sum
    tail = tail.next;

    l1 = l1 !== null ? l1.next : null;
    l2 = l2 !== null ? l2.next : null;
  }

  return dummy.next;
}

Complexity

  • Time: O(max(n, m)). One synchronized pass, bounded by the length of the longer list.
  • Space: O(max(n, m)) for the output list; O(1) beyond the output, since only the running carry needs to be tracked.

Watch out for

  • Keep looping until both input lists are exhausted, not just the shorter one: treat a finished list as supplying zero rather than stopping early.
  • A leftover carry after both lists end needs one more node appended to the result; skipping this is a common off-by-one.
  • Build the result with a dummy head node so appending digits does not require special-casing the very first digit.

Pattern

This is a digit-by-digit simulation with carry propagation, the same mental model behind adding binary strings or arbitrary-precision integers by hand: it applies anywhere a sequence needs to be processed position by position while state flows forward between positions.

Related questions