Add 1 to a Linked List Number

You are given the head of a singly linked list where every node holds a single digit (0–9). Reading the nodes from head to tail spells out a non-negative integer — the head is the most significant digit.

Add 1 to that number and return the result as an integer.

For example, 4 -> 5 -> 6 represents 456, and adding one gives 457. A list like 0 -> 0 -> 1 represents 1, so the answer is 2 — since we return the number, any leading zeros simply drop away.

Hints

· Stuck? Reveal one nudge at a time.

Adding 1 usually changes just the last digit — when does the change ripple further left?

A digit that is 9 becomes 0 and passes a carry along. Find the rightmost digit that isn't a 9.

Bump that last non-nine digit, reset every 9 after it to 0, and handle the all-nines case with a new leading node.

Common doubts

Because the list is read left to right as a written number: the first node is the leftmost, highest-place digit.

They form a small number — 001 is just 1 — so adding 1 gives 2. Since we return the number, leading zeros simply disappear.

Interview follow-ups

· What an interviewer asks next.

Same odometer logic, but skip the final read-off and return the head. For the all-nines case you return the new leading node you prepended.

Reverse both lists (or recurse to the tail), add digit by digit with a running carry, and build the result — the carry mechanics are this same idea generalized to two operands.

Fun facts

This is the odometer problem in disguise — the same rollover logic that turns 99,999 miles into 100,000 on a car's dial.
The trailing-nines trick reappears in the 'plus one' array problem and inside big-integer increment routines in real math libraries.

Asked at

AmazonMicrosoftAdobeGoogleFlipkart

Frequently Sometimes Occasionally

Example 1

Input: head = 4 -> 5 -> 6
Output: 457
4->5->6 represents 456; 456 + 1 = 457.

Example 2

Input: head = 1 -> 2 -> 3
Output: 124
1->2->3 represents 123; 123 + 1 = 124.

Example 3

Input: head = 0 -> 0 -> 1
Output: 2
0->0->1 represents 001 = 1; adding 1 gives 2. Leading zeros vanish because we return the number.

Constraints

- 1 <= number of nodes <= 9 - 0 <= value of each node <= 9 - The head node holds the most significant digit.

Adding 1 to a number is second nature on paper — but here the digits live in a linked list, most significant first, so the carry has to travel right to left while the list only points left to right. This tutorial builds from the obvious numeric shortcut to a clean odometer trick that never overflows.

Prerequisites

Before you start

· Concepts used directly in the solution.

Linked list traversal. Walking node to node with a pointer until you reach null.

Place value. A digit's worth depends on its position — the head is the highest place, the tail the ones place.

Carry propagation. When a digit rolls past 9 it resets to 0 and pushes a carry onto its left neighbour.

Clarifying questions

Asking before you code shows you understand the shape of the input — a small habit that separates seniors from coders who dive straight in.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is the most significant digit at the head?”

Yes — if it were at the tail the entire carry direction would flip.

“Is the list guaranteed non-empty?”

Confirm at least one node, otherwise the number is undefined.

Edge cases

“What if every digit is a 9?”

The number gains a digit — 99 becomes 100 — so a new leading node must appear.

“Can there be leading zeros like 0 to 0 to 1?”

Yes — treat them as an ordinary small number; 001 is just 1.

Constraints and scale

“How long can the list be?”

Short enough that the number fits in a machine integer, so a numeric approach stays safe here.

The ideal opening — say it like this

Before I code, let me confirm a couple of assumptions.

The head holds the most significant digit, correct?

And if the list is all nines, I should add a new leading node for the extra digit.

Understand the problem

In plain English: the list spells a number from head to tail. Return that number plus one.

Worked example

head: 4 -> 5 -> 6      represents 456
add 1                  456 + 1 = 457
answer: 457

head: 1 -> 9 -> 9      represents 199
last non-9 is the '1'  bump it -> 2, reset trailing 9s -> 0 0
result: 2 -> 0 -> 0    = 200

Key observations

1Aha

The carry stops at the first non-9 from the right

Adding 1 flips a trailing run of 9s to 0s and increments the single digit just before that run. Every digit further left is untouched.

1 2 9 9   + 1
    ^ ^   these 9s become 0 0
  ^       this 2 becomes 3
= 1 3 0 0

2Aha

All nines is the only case that grows the list

If there is no non-9 digit anywhere, the answer needs one more digit: a leading 1 followed by all zeros (9 9 becomes 1 0 0).

3Aha

No reversal required

Scan once to remember the rightmost non-9 node. Then bump it and zero the tail in a second pass — the carry is handled without ever reversing the list.

Brute force vs optimal

	Convert to number	Odometer in-place
Time	O(n)	O(n)
Space	O(1)	O(1)
Overflow risk	Yes on long lists	None — digit by digit

Both run in linear time; the difference is robustness. The full code for each lives in the Approaches selector below.

Summary

Key takeaway

To add 1 to a digit list, find the rightmost digit that isn't 9, increment it, and reset the trailing 9s to 0 — only an all-nines number needs a new leading digit.

scan list, remember last node with val != 9
if none:                 # all nines
    prepend node(1); set every old node to 0
else:
    last_non_nine.val += 1
    set every node after it to 0
return number spelled by the list