AlgoViz
HomeLinked List

Add one to a number represented by LL

Medium

Reverse, add with carry, reverse back

Problem

Given the head of a singly linked list representing a positive integer number. Each node of the linked list represents a digit of the number, with the 1st node containing the leftmost digit of the number and so on. The task is to add one to the value represented by the linked list and return the head of a linked list containing the final value. The number will contain no leading zeroes except when the value represented is zero itself.

In simple words

Add 1 at the last node and carry leftward; if the head carries over, add a new leading 1.

The idea

Addition works from the least significant digit, which is the tail here, so reverse the list, add one propagating the carry, and reverse back. If a carry survives the last digit, prepend a new node holding 1.

The trick

  • Stop propagating as soon as a digit is below 9 after incrementing.
  • A list of all 9s grows by one node.
  • Recursion can carry backwards instead, avoiding both reversals.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
0
1
2

Step 1 of 2. Here's the example — head -> 1 -> 2 -> 3 Values: 1, 2, 3.

1/2
Optimal
timeO(n)spaceO(1)
1reverse the list2carry = 1; cur = head3while cur and carry:4  s = cur.val + carry; cur.val = s % 10; carry = s / 10; prev = cur; cur = cur.next5if carry: prev.next = Node(1)6reverse back and return

Input

array
[1, 2, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3
Output:
1 -> 2 -> 4
Explanation:
123 + 1 = 124.

Example 2

Input:
list = 9 -> 9
Output:
1 -> 0 -> 0
Explanation:
99 + 1 = 100, carrying all the way.

Example 3

Input:
list = 5
Output:
6
Explanation:
5 + 1 = 6.

Constraints

  • 0 <= number of nodes in the Linked List <= 10^5
  • 0 <= ListNode.val <= 9
  • No leading zeroes in the value represented.

Practice this problem:LeetCode (premium)(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.