L11. Add 1 to a Number Represented by a Linked List

Adding $1$ to a number represented as a singly linked list is a classic data structures and algorithms interview problem that highlights the tension between iterative pointer manipulations and recursive backtracking. When digits are stored sequentially in a forward-facing singly linked list, standard addition mathematics (which requires right-to-left propagation of carries) forces us to rethink how we traverse and mutate our nodes.

1. Why Do We Need This? (Problem Statement)

You are given the head of a singly linked list where every single node contains a single decimal digit (0 through 9). Collectively, these nodes represent an integer. Your goal is to add $1$ to this number and return the head of the updated linked list.

Concrete Examples

• Example 1 (Same Number of Digits):

  • Input list: 1 -> 5 -> 9 (Represents the number 159)
  • Add $1$: 159 + 1 = 160
  • Output list: 1 -> 6 -> 0

• Example 2 (Cascading Carries & Extra Digit):

  • Input list: 9 -> 9 -> 9 -> 9 (Represents the number 9999)
  • Add $1$: 9999 + 1 = 10000
  • Output list: 1 -> 0 -> 0 -> 0 -> 0 (Requires allocating a brand new node for the leading carry).

2. Core Mental Model & The Backward Traversal Constraint

Basic elementary addition always starts from the least significant digit (rightmost) and moves toward the most significant digit (leftmost).

Real-Life Analogy

Imagine carrying a stack of plates or processing a paper number roll where you can only look forward. If you are given a singly linked list 1 -> 5 -> 9, your head pointer points to 1. You can easily walk forward from 1 to 5 to 9, but once you reach 9, you have no backward pointers (prev) to return to 5 and 1.

Because a singly linked list only allows forward traversal, we face a fundamental structural mismatch: addition requires right-to-left processing, but our pointers only move left-to-right.

3. The Naive Approach: Reversing the Linked List

To solve the direction mismatch without extra data structures, we can temporarily reverse the linked list so that the least significant digit sits at the head.

Step-by-Step Evolution (Iterative 3-Step Strategy)

1. Reverse the Linked List: Transform 1 -> 5 -> 9 into 9 -> 5 -> 1 -> null. Now the ones-place (9) is at the head.
2. Traverse & Add: Initialize a carry = 1. Walk through the reversed list, adding the carry to each node's data. If a node's value reaches $10$, set its data to $0$ and keep carry = 1. If the sum is less than $10$, set carry = 0 and break out early.
3. Reverse Back & Return: Restore the linked list to its original orientation by reversing it a second time, then return the head.

Note on Edge Cases (e.g., 9 -> 9 -> 9): If your traversal finishes and carry == 1 is still true (meaning you ran out of nodes while carrying a $1$), you must append a new node containing 1 at the correct position during or after restoration.

4. Complexity Analysis of the Iterative Approach

While the iterative reversal approach uses $O(1)$ auxiliary space, it requires traversing the list three separate times:

An interviewer may ask: "Can we solve this in a single pass without mutating/reversing links iteratively?" This leads us to Recursion and Backtracking.

5. The Optimal Approach: Recursive Backtracking

Instead of physically reversing pointers, we can let the recursive call stack act as our implicit backward pointer.

How Recursion Solves the Direction Problem

1. We dive deep into the linked list from the head (1) down to the tail (9), and finally past the tail to null.
2. When we hit null (our base case), we return an initial carry of 1.
3. As the recursion unwinds (backtracking), we process each node from right to left, updating node values and passing carries upward.

Recursive Execution Flow

6. Complete Recursive Implementation

Below is the clean, production-grade recursive implementation in Java demonstrating helper functions, base cases, and carry management.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class AddOneToLinkedList {

    public ListNode addOne(ListNode head) {
        // Trigger recursive helper and capture final carry from the head
        int finalCarry = helper(head);
        
        // If a carry remains after reaching the most significant digit,
        // we must create a new leading node (e.g., 999 + 1 = 1000)
        if (finalCarry == 1) {
            ListNode newNode = new ListNode(1);
            newNode.next = head;
            return newNode;
        }
        
        return head;
    }

    private int helper(ListNode temp) {
        // Base Case: Reached past the tail, bubble up initial carry of 1
        if (temp == null) {
            return 1;
        }
        
        // Recursively dive deeper to reach the tail (least significant digit)
        int carry = helper(temp.next);
        
        // Backtracking phase: Add carry to current node's value
        int sum = temp.val + carry;
        
        if (sum < 10) {
            temp.val = sum;
            return 0; // No further carry needed
        } else {
            temp.val = 0; // Set current digit to 0 and propagate carry = 1
            return 1;
        }
    }
}

7. Step-by-Step Recursive Dry Run (9 -> 9 -> 9)

Let us trace what happens when our input list is 9 -> 9 -> 9:

1. addOne(head) calls helper(node at first 9).
2. helper recursively calls helper for the second 9, then the third 9, and finally helper(null).
3. Base Case Reached: temp == null returns carry = 1 to the third 9.
4. Third 9 (Backtracking 1):
   • sum = 9 + 1 = 10.
   • temp.val = 0, returns carry = 1.
5. Second 9 (Backtracking 2):
   • sum = 9 + 1 = 10.
   • temp.val = 0, returns carry = 1.
6. First 9 (Backtracking 3):
   • sum = 9 + 1 = 10.
   • temp.val = 0, returns carry = 1.
7. Control returns to addOne:
   • finalCarry is 1.
   • A new node 1 is created: 1 -> 0 -> 0 -> 0.
   • Returns the new head.

8. Complexity Summary: Iterative vs. Recursive

Summary and Key Takeaways

• The Direction Mismatch: Singly linked lists restrict movement to forward-only traversal, conflicting with right-to-left addition mathematics.
• Iterative Solution Strategy: Involves reversing the list, performing linear addition with a carry, and reversing the list back to its original orientation ($O(3N)$ time, $O(1)$ space).
• Early Termination: In the iterative approach, if carry == 0 during traversal, you can immediately break out of the loop, saving unnecessary iterations.
• Recursive Backtracking: Leverages the call stack to process nodes from tail to head without physically modifying pointer directions.
• Leading Carry Handling: If the most significant digit produces a carry of $1$ (e.g., transforming 999 into 1000), a new head node must be allocated and linked.
• Space-Time Trade-off: The iterative approach trades extra code complexity for $O(1)$ space, whereas the recursive approach trades call stack space ($O(N)$) for cleaner, elegant single-pass code.