← DSA Atlas
Dedicated problem page · #2

Add Two Numbers

MediumLinked Lists and Pointer ManipulationDigit-by-digit addition with carryLinked list traversal simulating grade-school addition
Solve on LeetCode ↗
02
MediumLinked Lists and Pointer ManipulationLinked list traversal simulating grade-school additionDigit-by-digit addition with carry

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers, with digits stored in reverse order (ones digit first) and each node holding a single digit. Add the two numbers and return the sum as a linked list in the same reverse-order form.

Open official problem prompt ↗
In plain English

Compute the sum of two integers given as reversed digit lists and return the result in the same reversed-list form.

Picture it like this

Adding two numbers on paper starting from the rightmost column, carrying a 1 into the next column whenever a column total reaches ten.

Example
Input
l1 = [2, 4, 3], l2 = [5, 6, 4]
Output
[7, 0, 8]
Why
l1 represents 342 and l2 represents 465; 342 + 465 = 807, which stored ones-first is [7, 0, 8].
Constraints
The number of nodes in each list is in the range [1, 100]0 <= Node.val <= 9Each number has no leading zeros except the number 0 itself
Pattern lesson

See the pattern, then code

Digit-by-digit addition with carry
Recognition clue

Digits stored ones-first with a possible carry between positions is exactly column addition, done as a single synchronized walk over both lists.

↗
Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. Because the least significant digit comes first, you can add corresponding nodes left to right just like adding by hand, propagating a carry into the next position.

New words, made simpleKnow these before the algorithm
Carry
The overflow digit passed to the next-higher position when a column sum is 10 or more.
Dummy head
A placeholder node that simplifies appending; the real list is dummy.next.
Reverse-order digits
Storage where the ones digit is the head node.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Convert to integers, add, rebuild list

Works in Python's big ints but fails the spirit and can overflow in fixed-width languages.

Read both lists into ints, sum them, then split the result into digits.

Time O(m+n)Space O(m+n)
Best choiceSingle-pass carry addition

Handles unequal lengths and final carry cleanly; the intended solution.

Add node by node with a carry, building the result as you go.

Time O(max(m,n))Space O(max(m,n))
The rule we keep true

Invariant

After processing position i, the nodes built so far represent the correct low-order digits of the sum and carry holds the overflow into position i+1.

Why this is correct

Reasoning

Reversed storage aligns least-significant digits at the heads, so column addition proceeds head to tail; the loop's 'or carry' clause guarantees a trailing carry (like 9+1=10) becomes its own final node.

The algorithm in three movesSay these aloud before coding
1Create a dummy head and a running carry of 0

2+5=7, carry 0 -> 7

2Walk both lists together, summing the two current digits plus carry

4+6=10, carry 1 -> 0

3Append total % 10 as a new node and set carry to total // 10

3+4+1=8, carry 0 -> 8

4Continue while either list has nodes or carry is nonzero

5Return dummy.next

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
2+50
4+61
3+42
1 · Read2 + 5 + 0
2 · AskDigit and carry?
3 · Update statetotal=7
4 · Resultappend 7, carry=0
Key takeaway

Each column adds the two digits plus the incoming carry, producing one output digit and a carry into the next column.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-5Set up

    A dummy node anchors the output and carry starts at 0.

  2. 2
    Lines 6-9Read the column

    Treat a missing node as 0 so unequal lengths just work, then sum with carry.

  3. 3
    Lines 10-16Emit digit, advance

    Append total % 10, update carry to total // 10, and step each list forward if present.

  4. 4
    Lines 17Return

    Skip the dummy to return the real head.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Lists of different lengths
  • A final carry that adds a new most-significant digit (e.g. [9] + [1] = [0,1])
  • One number is 0 (single node with value 0)
!

Common beginner mistakes

  • Ending the loop before flushing a leftover carry
  • Assuming both lists have equal length and dereferencing a None node
  • Forgetting to advance l1 or l2 only when they still have nodes
Check your understanding

Why include 'or carry' in the loop condition?

More in Linked Lists and Pointer Manipulation

#206Reverse Linked ListIterative pointer reversal#141Linked List CycleFast and slow pointers (Floyd's cycle detection)#143Reorder ListFind middle, reverse second half, merge alternately#138Copy List with Random PointerClone with old-to-new node mapping#146LRU CacheHash map plus recency-ordered structure#19Remove Nth Node From EndFixed-gap two pointers