How do you solve Add Two Numbers?

Use a dummy head node to simplify list construction. Initialize carry to zero. Loop while either list has nodes or carry is non-zero. At each iteration, extract values from current nodes or zero if none, sum with carry, update carry, create a new node with the digit, and advance pointers. Return the next node of dummy head as the result.

Add Two Numbers

Q: What is the time complexity of Add Two Numbers?

O(max(m, n)). The algorithm traverses both linked lists once, where m and n are their lengths. Each node is processed exactly once.

Q: What pattern does Add Two Numbers use?

The Pattern: Linked List (Digit-by-Digit Simulation) The Heuristic: When adding numbers represented as linked lists in reverse order, simulate elementary addition by traversing both lists simultaneously, summing digits and carry, and building the result list on the fly without converting to integers.

Medium In-place Reversal of a Linked List

Problem

Given two non-empty linked lists representing two non-negative integers in reverse order, return a linked list representing their sum in the same reverse order format, where each node contains a single digit. You may assume the two numbers do not contain any leading zeros, except the number 0 itself.

The number of nodes in each linked list is in the range [1, 100]
0 ≤ Node.val ≤ 9
It is guaranteed that the list represents a number that does not have leading zeros

Example

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

The numbers represented are 342 and 465. Adding them yields 807. The output linked list represents 708 in reverse order. The algorithm iterates through both lists simultaneously, adding corresponding digits and carrying over any overflow. At index 0, 2 + 5 = 7 with no carry. At index 1, 4 + 6 = 10, so 0 is stored and carry 1 is forwarded. At index 2, 3 + 4 + 1 (carry) = 8, stored as is. The final linked list is [7,0,8].

Approach

Straightforward Solution

Convert both linked lists to integers, sum them, and then convert back to a linked list. This approach is inefficient and can cause integer overflow for very large numbers.

Core Observation

Adding two numbers digit-by-digit from least significant to most significant is analogous to traversing two linked lists simultaneously, summing node values and carrying over any overflow to the next digit.

Path to Optimal

Preview

The key insight is to simulate the addition process as done by hand: iterate through both linked lists simultaneously, sum the digits along with any carry, create a new node for the digit part of the sum, and carry over the remainder…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a dummy head node to simplify list construction. Initialize carry to zero…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(max(m, n))

The algorithm traverses both linked lists once, where m and n are their lengths. Each node is processed exactly once.

Space

O(max(m, n))

The output linked list can be at most one node longer than the longer input list due to carry. The auxiliary space is O(1) excluding the output list.

Pattern Spotlight

Linked List (Digit-by-Digit Simulation)

When adding numbers represented as linked lists in reverse order, simulate elementary addition by traversing both lists simultaneously, summing digits and carry, and building the result list on the fly without converting to integers.

Solution

Python

1class Solution:
  def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
      dummy = ListNode()
      curr = dummy
      carry = 0
6
      while l1 or l2 or carry:
          v1 = l1.val if l1 else 0
          v2 = l2.val if l2 else 0
10
          val = v1 + v2 + carry
          carry = val // 10
          val = val % 10
          curr.next = ListNode(val)
15
          curr = curr.next
          l1 = l1.next if l1 else None
          l2 = l2.next if l2 else None
      
      return dummy.next

Step-by-Step Solution

Initialize Dummy Head, Current Pointer, and Carry

3dummy = ListNode()
4curr = dummy
5carry = 0

Objective

To set up the initial state for building the result linked list and tracking carry during addition.

Key Insight

Using a dummy head node simplifies edge cases by providing a fixed starting point for the result list, avoiding special handling for the first node. Initializing carry to zero prepares for the addition process, ensuring correct propagation of overflow digits.

Interview Quick-Check

Core Logic

The dummy node acts as a sentinel to simplify list construction, allowing uniform insertion of new nodes.

State & Boundaries

Carry must be initialized to zero to correctly accumulate overflow from digit sums.

Traverse Both Lists and Accumulate Sum with Carry

To iterate through both input lists simultaneously, summing corresponding digits and carry, and appending the result digit to the output list.

Return the Result Linked List Skipping Dummy Head

To return the head of the newly constructed linked list representing the sum.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 7 Critical

while l1 or l2 or carry:

Continue looping while there are nodes in l1 or l2 or a non-zero carry.

This loop condition guarantees processing all digits and any leftover carry, handling lists of unequal length and final overflow.

Line 12 Critical

carry = val // 10

Update carry by dividing sum by 10 (integer division).

Carry is the overflow digit to be added in the next iteration, ensuring correct multi-digit addition.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why must the loop continue while there is a carry even if both input lists are exhausted?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Add Two Numbers from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Add Two Numbers drill

or drill a free problem

1	`class Solution:`
2	`def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:`
3	`dummy = ListNode()`
4	`curr = dummy`
5	`carry = 0`
6
7	`while l1 or l2 or carry:`
8	`v1 = l1.val if l1 else 0`
9	`v2 = l2.val if l2 else 0`
10
11	`val = v1 + v2 + carry`
12	`carry = val // 10`
13	`val = val % 10`
14	`curr.next = ListNode(val)`
15
16	`curr = curr.next`
17	`l1 = l1.next if l1 else None`
18	`l2 = l2.next if l2 else None`
19
20	`return dummy.next`