# 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: ```text 1 -> 2 -> 3 ``` represents the number: ```python 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 | Item | Meaning | |---|---| | Input | Head of a singly linked list | | Output | Head of the linked list after adding one | | Digit order | Most significant digit first | | Node values | `0` through `9` | | List length | `1` to `100` | Example function shape: ```python def plusOne(head: Optional[ListNode]) -> Optional[ListNode]: ... ``` ## Examples Example 1: ```text 1 -> 2 -> 3 ``` This represents `123`. After adding one: ```python 123 + 1 = 124 ``` The output is: ```text 1 -> 2 -> 4 ``` Example 2: ```text 1 -> 2 -> 9 ``` This represents `129`. After adding one: ```python 129 + 1 = 130 ``` The output is: ```text 1 -> 3 -> 0 ``` Example 3: ```text 9 -> 9 -> 9 ``` This represents `999`. After adding one: ```python 999 + 1 = 1000 ``` The output is: ```text 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 `9`s cause carry propagation. For example: ```text 1 -> 2 -> 9 -> 9 ``` Adding one gives: ```text 1 -> 3 -> 0 -> 0 ``` The last non-`9` digit before the trailing `9`s is `2`. We increment it to `3`. Then every digit after it becomes `0`. So the main task is: ```text 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: ```text 9 -> 9 -> 9 ``` create: ```text 0 -> 9 -> 9 -> 9 ``` The rightmost non-`9` node is the dummy `0`. Increment it: ```text 1 -> 9 -> 9 -> 9 ``` Set all following nodes to `0`: ```text 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 `9`s 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 `9`s, 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 `9`s, 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. | Metric | Value | Why | |---|---:|---| | Time | `O(n)` | We traverse the list once, then zero out a suffix | | Space | `O(1)` | Only a few pointers are used | ## Implementation ```python # 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-`9`s case: ```python dummy = ListNode(0) dummy.next = head ``` We start `target` at the dummy: ```python target = dummy ``` Then we scan the original list: ```python 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: ```python target.val += 1 ``` Every node after `target` was a trailing `9`, so it becomes `0`: ```python 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: ```python if dummy.val == 1: return dummy ``` Otherwise, skip it: ```python return dummy.next ``` ## Testing ```python 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: | Test | Why | |---|---| | `[1,2,3]` | No carry chain | | `[1,2,9]` | Carry through one trailing `9` | | `[9,9,9]` | Creates a new leading node | | `[0]` | Smallest number | | `[8,9,9]` | Carry through multiple trailing `9`s |