Add Two Numbers Linked List

The problem

Two non-negative integers are stored as singly linked lists, digits in reverse order (ones place at the head). Return their sum as a linked list in the same format.

l1: 2 → 4 → 3   // 342
l2: 5 → 6 → 4   // 465
sum: 7 → 0 → 8  // 807

Constraints usually: no leading zeros except 0 itself; lists can differ in length.

Frontend parallel: carrying through digit streams, big-int add when you only get iterators of digits.

Brute force (say it, then skip)

Convert both lists to numbers, add, write digits back. Breaks on big integers in languages with fixed ints; in JS Number overflows past 2^53. Don’t ship this in an interview unless constraints are tiny.

// fragile — only for tiny values
function addTwoNumbersBrute(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const toNum = (n: ListNode | null) => {
    let s = "", cur = n;
    while (cur) { s = String(cur.val) + s; cur = cur.next; }
    return BigInt(s || "0");
  };
  let sum = toNum(l1) + toNum(l2);
  const dummy = new ListNode(0);
  let tail = dummy;
  if (sum === 0n) return dummy;
  while (sum > 0n) {
    tail.next = new ListNode(Number(sum % 10n));
    tail = tail.next;
    sum /= 10n;
  }
  return dummy.next;
}

Time	O(max(m, n))
Space	O(max(m, n)) for string/bigint

Optimal: walk both lists with carry

Create a dummy head. While either list has nodes or carry is non-zero:

1. Sum = carry + (l1?.val ?? 0) + (l2?.val ?? 0)
2. New digit = sum % 10, carry = floor(sum / 10)
3. Advance pointers that exist

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(0);
  let tail = dummy;
  let carry = 0;

  while (l1 || l2 || carry) {
    const sum = carry + (l1?.val ?? 0) + (l2?.val ?? 0);
    carry = Math.floor(sum / 10);
    tail.next = new ListNode(sum % 10);
    tail = tail.next;
    l1 = l1?.next ?? null;
    l2 = l2?.next ?? null;
  }

  return dummy.next;
}

Time	O(max(m, n))
Space	O(max(m, n)) for the result (O(1) extra)

Walk 342 + 465

step	digits	carry in	sum	write	carry out
1	2+5	0	7	7	0
2	4+6	0	10	0	1
3	3+4	1	8	8	0

Result 7 → 0 → 8.

Unequal lengths: 999 + 1

Lists: 9→9→9 and 1. After three digits carry is still 1 → append a final 1 → 0→0→0→1 (1000). Forgetting final carry is the #1 bug.

Edge cases

• One list empty → return the other (plus any carry path still works)
• Both single zero → 0
• All nines → one extra node
• Different lengths — null-safe ?.val ?? 0

Common mistakes

• Mutating input lists without clarifying (usually build a new list)
• Using / 10 without floor in languages that do float division
• Stopping when both lists end but carry remains
• Writing numbers forward then reversing unnecessarily

Interview delivery

1. Confirm reverse digit order and non-negative.
2. Reject “convert to int” for large inputs.
3. Dummy + carry loop.
4. Trace unequal length + final carry.
5. O(max(m,n)) time, O(1) extra space.

Related

• Reverse Linked List
• Merge Two Sorted Lists
• Linked List Cycle
• Copy List with Random Pointer
• JavaScript Interview Guide

Further reading

• LeetCode 2 — Add Two Numbers
• MDN: Math.floor