Add Two Numbers

Intuition

We want to simulate the way we add numbers by hand, digit by digit, from the least significant to the most significant digit (right to left).

• Each linked list represents a number in reverse order.
• We sum corresponding digits, keep track of the carry, and move to the next nodes.

Approach

• Initialize a dummy head node to simplify list creation.
• Use pointers l1 and l2 to traverse both linked lists.
• Maintain a carry variable (initially 0).
• For each pair of nodes:
  • Compute sum = (l1 value) + (l2 value) + carry.
  • New digit = sum % 10.
  • Update carry = Math.floor(sum / 10).
  • Add the new digit as a node to the result list.
• If carry remains after processing both lists, append it as a new node.
• Return the list starting from dummyHead.next.

Proof of Correctness

• Digit-by-digit correctness: Each digit is processed independently with carry handled explicitly, so the resulting sum matches the arithmetic addition.
• Termination: The algorithm stops when both linked lists and carry are processed, so no digit is left unaccounted.
• Order correctness: Since digits are stored in reverse order, processing from head to tail correctly constructs the final number.

Complexity

• Time:
  • We traverse each list once, where m and n are lengths of l1 and l2.
  • Total: 0(max(m,n)).
• Space:
  • Output list stores the sum; extra variables are constant.
  • Total: 0(max(m,n)).

Code

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

  while (l1 || l2) {
    const x = l1 ? l1.val : 0;
    const y = l2 ? l2.val : 0;

    const sum = x + y + carry;
    carry = Math.floor(sum / 10);

    current.next = new ListNode(sum % 10);
    current = current.next;

    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }

  if (carry > 0) {
    current.next = new ListNode(carry);
  }

  return dummyHead.next;
}

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy_head = ListNode(0)
    current = dummy_head
    carry = 0

    while l1 or l2:
        x = l1.val if l1 else 0
        y = l2.val if l2 else 0

        sum_val = x + y + carry
        carry = sum_val // 10

        current.next = ListNode(sum_val % 10)
        current = current.next

        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    if carry > 0:
        current.next = ListNode(carry)

    return dummy_head.next