Plus One Linked List - Solution & Explanation

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.