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 node contains a single digit. Add the two numbers and return the sum as a linked list in the same reverse order.

Why this is worth learning

Reverse digit order makes ordinary column addition streamable. The carry is the only information that must pass from one digit position to the next.

Before coding: one-minute experiment

What reverse-order digit list results from [9,9] plus [1]?

Function signature

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode

Inputs / outputs

• l1, l2: heads of the linked lists.
• Return: head of the sum list.

Example

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

Constraints

• 1 <= number of nodes <= 100_000
• Each node is 0-9.

Core idea (near-solution)

One baseline converts both lists to integers and adds them, but long inputs can represent numbers larger than any Go integer even though each digit is small. Work in the representation already supplied: the head is the ones column. After emitting a column's last decimal digit, only its overflow can affect later columns. That overflow is the carry; no earlier digit needs to be retained. Two digits and carry sum to at most 19, so local arithmetic stays small regardless of list length. The result is newly allocated because addition must leave both operands intact.

Invariant: carry always holds the overflow from the previous digit.

Algorithm (step-by-step)

1. Initialize dummy head, carry = 0.
2. While l1 or l2 is not nil or carry > 0:
   • Sum digit values plus carry.
   • Create a new node with sum % 10.
   • Update carry = sum / 10.
   • Move l1 and l2 forward if available.
3. Return dummy.Next.

Correctness sketch

Before processing digit position i, the output contains the correct low i digits of the sum and carry is the amount owed to position i. Read each available input digit, treating an exhausted list as zero, and add them with carry. Division by ten produces the next carry and remainder modulo ten produces exactly the current decimal digit. Appending a new node preserves the arithmetic invariant and leaves the inputs untouched. Continue while either input or carry remains; otherwise a final carry would be lost. When all three are exhausted, no higher contribution remains, so the output represents the full sum.

Trace (hand walkthrough)

Example input:
(2 -> 4 -> 3) + (5 -> 6 -> 4)
= 342 + 465 = 807
Output: 7 -> 0 -> 8

Walk:
- 2+5=7 -> node 7, carry=0
- 4+6=10 -> node 0, carry=1
- 3+4+1=8 -> node 8, carry=0 -> 7->0->8

Pitfalls to avoid

• Forgetting a final carry node.
• Stopping when one list ends (the other may continue).

Debugging lens

Test unequal lengths, cascading carry, zero, and input preservation. Do not convert a 100000-digit list to a machine integer. The reference allocates a fresh result list.

Complexity

• Time: O(n)
• Extra space: O(n) for the output list.

Implementation notes (Go)

• Use a dummy head to build the result list cleanly.
• Loop while l1, l2, or carry remains; treat missing nodes as 0.
• Compute sum := a + b + carry, then carry = sum/10, digit = sum%10.

Contract precision

Both inputs are finite digit lists. The reference does not mutate either input and allocates new result nodes. It preserves positions through the longer input even when high-order input digits are zero.

Reconstruction checkpoint

Work [8,9,9] plus [7,1] one column at a time. Name the output digit and carry after each column, including any column with no input node.

Return to Linked List · Module quiz