Workspace

Problem workspace

3 day streakD

Add Two Numbers

MediumLinked ListsConstruction

The challenge

Add two nonnegative integers represented as reversed base-10 digit lists. Return a new reversed digit list.

Each value is a digit 0…9. Empty inputs represent zero. Inputs are not modified.

Example

[2, 4, 3] + [5, 6, 4] represents 342 + 465 → [7, 0, 8].

Use the walkthrough below to inspect the input and each state change.

See Add two numbers, step by step

Follow the pointers. Watch each link change.

6 nodes · singly linkedIDs = node identity · ∅ = null
342 + 465: Read the inputIDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links. Node positions stay fixed while arrows change. The pointer strip and node table below give the same state in text.head · headA2A14A23A3∅headB5B16B24B3∅
CurrentResultYellow arrow: changed next link
headA1headAA1headBB1
Inspect node links
Each row is a distinct node object. D is the dummy sentinel.
NodeValueNext
A12A2
A24A3
A33null
B15B2
B26B3
B34null
Step 01 / 5

Read the input

IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.

Start from the input head pointers.
View original input

A: 2 (A1) → 4 (A2) → 3 (A3); B: 5 (B1) → 6 (B2) → 4 (B3); parameters: {}

Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.

Put it into code

At each position, append sum modulo 10 and carry sum divided by 10.

Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def add_numbers(a, b):
    dummy = Node()
    tail, carry = dummy, 0
    while a or b or carry:
        total = carry
        if a:
            total += a.val
            a = a.next
        if b:
            total += b.val
            b = b.next
        carry, digit = divmod(total, 10)
        tail.next = Node(digit)
        tail = tail.next
    return dummy.next if dummy.next else Node(0)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap