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.

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)

Simulate digit-by-digit addition with a carry.

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

• Invariant: carry always holds the overflow from the previous digit.
• Pointer rewiring preserves all nodes and changes only their order or links.
• Each step maintains list connectivity and the intended invariant.
• When the traversal ends, the list structure matches the required transformation.

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).

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.