Leetcode 369. Plus One Linked List Python
Plus One Linked List - Video Solution
Watch 6 video solutions for Plus One Linked List, a medium level problem involving Linked List, Math. This walkthrough by TechZoo has 644 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given a non-negative integer represented as a linked list of digits, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list.
Example 1:
Input: head = [1,2,3] Output: [1,2,4]
Example 2:
Input: head = [0] Output: [1]
Constraints:
- The number of nodes in the linked list is in the range
[1, 100]. 0 <= Node.val <= 9- The number represented by the linked list does not contain leading zeros except for the zero itself.
Approach Overview
Problem Overview: A non‑negative integer is stored as a singly linked list where each node contains a single digit. The most significant digit appears first. Add one to the number and return the updated list while correctly handling carry propagation such as 1→2→9 becoming 1→3→0.
Approach 1: Reverse List + Add One (O(n) time, O(1) space)
Reverse the linked list so the least significant digit becomes the head. Perform the usual digit addition: add 1, propagate carry while digits equal 9, and stop once no carry remains. If a carry still exists after the final node, append a new node with value 1. Reverse the list again to restore the original order. This mirrors how addition works from right to left but requires two list reversals.
Approach 2: Recursion Carry Propagation (O(n) time, O(n) space)
Use recursion to reach the tail node first. When the recursive call returns, propagate the carry back toward the head. Each step updates node.val = (node.val + carry) % 10 and forwards (node.val + carry) / 10. If the head still produces a carry, prepend a new node with value 1. The logic is clean and closely models mathematical addition, but recursion consumes O(n) call stack space.
Approach 3: Last Non‑9 Traversal (O(n) time, O(1) space)
This is the optimal single‑pass technique. Traverse the list and track the last node whose value is not 9. Increment that node by one, then set every node after it to 0. If the list contains only 9s (for example 9→9→9), create a dummy node with value 0 before the head. After incrementing the dummy, the result becomes 1→0→0→0. This avoids reversing the list and avoids recursion while handling carry efficiently.
The key insight relies on how carry works in base‑10 numbers. Only the rightmost non‑9 digit actually changes; every trailing 9 becomes 0. Recognizing this pattern allows a single traversal using standard linked list iteration combined with simple math rules.
Recommended for interviews: The last non‑9 traversal approach. It runs in O(n) time with O(1) space and demonstrates strong understanding of carry propagation in linked lists. Reverse‑and‑add shows solid fundamentals, but the single‑pass technique is what most interviewers expect for a polished solution.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse List + Add One | O(n) | O(1) | When you want straightforward digit addition similar to array problems |
| Recursion Carry Propagation | O(n) | O(n) | When recursion is acceptable and code clarity is preferred |
| Last Non-9 Traversal | O(n) | O(1) | Optimal approach for interviews and production due to single traversal and constant memory |