LeetCode 369: Plus One Linked List

Problem Restatement

We are given the head of a non-empty singly linked list.

The linked list represents a non-negative integer.

Each node stores one digit from 0 to 9.

The digits are stored in normal order, so the most significant digit is at the head.

For example:

1 -> 2 -> 3

represents the number:

123

We need to add 1 to this number and return the head of the resulting linked list.

The number has no leading zero unless the number itself is 0. The official examples include [1,2,3] -> [1,2,4] and [0] -> [1].

Input and Output

Example function shape:

def plusOne(head: Optional[ListNode]) -> Optional[ListNode]:
    ...

Examples

Example 1:

1 -> 2 -> 3

This represents 123.

After adding one:

123 + 1 = 124

The output is:

1 -> 2 -> 4

Example 2:

1 -> 2 -> 9

This represents 129.

After adding one:

129 + 1 = 130

The output is:

1 -> 3 -> 0

Example 3:

9 -> 9 -> 9

This represents 999.

After adding one:

999 + 1 = 1000

The output is:

1 -> 0 -> 0 -> 0

First Thought: Reverse the List

One direct way is:

1. Reverse the linked list.
2. Add one from the least significant digit.
3. Propagate carry.
4. Reverse the list back.

This works, but it modifies the list structure twice.

We can solve it in one forward traversal without reversing.

Key Insight

Only trailing 9s cause carry propagation.

For example:

1 -> 2 -> 9 -> 9

Adding one gives:

1 -> 3 -> 0 -> 0

The last non-9 digit before the trailing 9s is 2.

We increment it to 3.

Then every digit after it becomes 0.

So the main task is:

find the rightmost node whose value is not 9

If every digit is 9, we need a new leading 1.

A dummy node solves this cleanly.

For:

9 -> 9 -> 9

create:

0 -> 9 -> 9 -> 9

The rightmost non-9 node is the dummy 0.

Increment it:

1 -> 9 -> 9 -> 9

Set all following nodes to 0:

1 -> 0 -> 0 -> 0

Return the dummy node because its value became 1.

Algorithm

1. Create a dummy node with value 0.
2. Link it before head.
3. Set target = dummy.
4. Traverse the list.
5. Whenever a node value is not 9, update target to that node.
6. After traversal, increment target.val.
7. Set every node after target to 0.
8. If dummy.val == 1, return dummy.
9. Otherwise, return dummy.next.

Correctness

The only digits affected by adding one are the trailing run of 9s and the digit immediately before that run.

If the number does not end in 9, the last digit is the rightmost non-9 digit. Incrementing it is enough.

If the number ends in one or more 9s, each trailing 9 becomes 0, and the carry moves left until it reaches the rightmost non-9 digit. That digit increases by one.

The algorithm finds exactly this rightmost non-9 node as target.

After incrementing target, all nodes after it must be trailing 9s, so setting them to 0 correctly applies the carry.

If all original digits are 9, the dummy node remains the rightmost non-9 node. Incrementing it creates the new leading 1, and all original nodes become 0.

Therefore, the returned linked list represents the original number plus one.

Complexity

Let n be the number of nodes.

Implementation

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def plusOne(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head

        target = dummy
        current = head

        while current:
            if current.val != 9:
                target = current
            current = current.next

        target.val += 1

        current = target.next
        while current:
            current.val = 0
            current = current.next

        if dummy.val == 1:
            return dummy

        return dummy.next

Code Explanation

The dummy node handles the all-9s case:

dummy = ListNode(0)
dummy.next = head

We start target at the dummy:

target = dummy

Then we scan the original list:

while current:
    if current.val != 9:
        target = current
    current = current.next

After this loop, target is the rightmost node that can absorb the carry.

We increment it:

target.val += 1

Every node after target was a trailing 9, so it becomes 0:

current = target.next
while current:
    current.val = 0
    current = current.next

If the dummy changed from 0 to 1, it is now part of the result:

if dummy.val == 1:
    return dummy

Otherwise, skip it:

return dummy.next

Testing

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

def build(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

def run_tests():
    s = Solution()

    assert to_list(s.plusOne(build([1, 2, 3]))) == [1, 2, 4]
    assert to_list(s.plusOne(build([1, 2, 9]))) == [1, 3, 0]
    assert to_list(s.plusOne(build([9, 9, 9]))) == [1, 0, 0, 0]
    assert to_list(s.plusOne(build([0]))) == [1]
    assert to_list(s.plusOne(build([8, 9, 9]))) == [9, 0, 0]

    print("all tests passed")

run_tests()

Test meaning: