Add Two Numbers

Interview Problem Intermediate Medium Same-direction Pointers Linked List

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.addTwoNumbers(l1, l2). Each list stores a nonnegative integer in reverse digit order. Return a new reverse-order digit list for their sum.

Starter code

class Solution:
    def addTwoNumbers(self, l1, l2):
        pass

Test cases

basic-sum

{
  "args": [
    {
      "$type": "linked-list",
      "values": [
        2,
        4,
        3
      ]
    },
    {
      "$type": "linked-list",
      "values": [
        5,
        6,
        4
      ]
    }
  ]
}

Expected: {"$type":"linked-list","values":[7,0,8]}

Wizard outline

Step 1: Initialize Solution.addTwoNumbers
Replace the empty starter with the first real state owned by Solution.addTwoNumbers. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Basic Sum case
Complete the readable core algorithm for one representative Interview case. Advance uneven lists independently and propagate carry through a sentinel-built result.
Step 4: Harden the Final Carry boundary
Repair the reviewed boundary and pass the complete submission contract. At each position the algorithm emits exactly the current decimal digit of both remaining numbers plus incoming carry and forwards the correct carry. Induction over positions yields every sum digit, including a final carry.

Footguns and prerequisites

A final carry after both inputs end requires one additional result node.
linked lists

Reviewed references

LeetCode 2 — Add Two Numbers

Practice prerequisites

Relink Nodes Safely(opens in a new tab)
Relink Nodes Safely isolates every untouched node keeps its original next link, and at most one predecessor changes to the removed node’s former successor. That focused state discipline is required when implementing add two numbers as a complete Interview Problem.

Recommended approach and implementation

Use a sentinel result tail and carry. While either list or carry remains, add available digits, create total%10, and retain total//10.

Why it works: At each position the algorithm emits exactly the current decimal digit of both remaining numbers plus incoming carry and forwards the correct carry. Induction over positions yields every sum digit, including a final carry.

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        sentinel = ListNode()
        tail = sentinel
        carry = 0
        while l1 or l2 or carry:
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next
            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next
        return sentinel.next