text
function plusOne(head):
    num = 0
    current = head
    while current is not null:
        num = num * 10 + current.val
        current = current.next
    
    num = num + 1
    
    return convertToLinkedList(num)

Analysis & Failure Point

• Time Complexity: $O(N)$, where $N$ is the number of nodes.
• Space Complexity: $O(N)$ to create the new list.
• Why it fails: This approach fails due to integer overflow. A linked list can hold an arbitrarily large number of digits (e.g., 100 nodes). Standard integer types (even 64-bit integers) cannot store numbers with more than ~19 digits. Consequently, this solution will crash or produce incorrect results for large inputs, resulting in a Runtime Error or Wrong Answer on LeetCode.

Core Insight for Plus One Linked List

The fundamental challenge in LeetCode 369 is the direction of the list versus the direction of addition.

• The linked list is singly linked and moves from Most Significant Bit (MSB) to Least Significant Bit (LSB).
• Mathematical addition proceeds from LSB to MSB (right to left).

To bridge this gap without reversing the list explicitly, we can utilize the call stack via recursion.

The recursion stack allows us to traverse strictly forward to the end of the list. As the recursion unwinds (returns), we effectively move backward from the tail to the head. This allows us to process the addition at the last node and propagate any carry to the previous node, exactly mimicking the manual addition process.

Visual Description: Imagine the recursion tree as a path diving deep into the list.

1. Descent: The function calls itself until it hits the null terminator after the last node.
2. Base Case: The bottom of the recursion (the end of the list) returns a "carry" of 1 (representing the +1 operation we need to perform).
3. Ascent: As the function returns to the parent node, it receives the carry from its child. It adds this carry to the current node's value. If the sum is 10, the current node becomes 0, and we return a carry of 1 up to the next parent. If the sum is less than 10, we update the value and return a carry of 0.

Execution Flow

Let's trace the algorithm with the input head = [1, 2, 9].

1. Call dfs(1): Calls dfs(2).
2. Call dfs(2): Calls dfs(9).
3. Call dfs(9): Calls dfs(null).
4. Base Case dfs(null): Returns 1 (the initial +1).
5. Back at Node 9:
   • Receives carry = 1.
   • sum = 9 + 1 = 10.
   • node.val becomes 10 % 10 = 0.
   • Returns carry = 10 / 10 = 1.
6. Back at Node 2:
   • Receives carry = 1.
   • sum = 2 + 1 = 3.
   • node.val becomes 3 % 10 = 3.
   • Returns carry = 3 / 10 = 0.
7. Back at Node 1:
   • Receives carry = 0.
   • sum = 1 + 0 = 1.
   • node.val becomes 1 % 10 = 1.
   • Returns carry = 1 / 10 = 0.
8. Main Function: dfs(head) returned 0. No new head needed.
9. Result: List is 1 -> 3 -> 0.

Proof of Correctness

The algorithm guarantees correctness by enforcing the invariant of standard addition: $Digit_{new} = (Digit_{old} + Carry_{in}) \pmod{10}$ and $Carry_{out} = \lfloor (Digit_{old} + Carry_{in}) / 10 \rfloor$.

• The base case introduces the +1 exactly at the least significant position.
• The recursive structure ensures that the carry from position $i$ is always processed at position $i-1$.
• The post-processing check ensures that if the most significant digit generates a carry (e.g., $99 + 1 = 100$), the list is correctly extended.

Reference Implementation

C++ Solution for LeetCode 369

cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // Helper function to perform DFS and return carry
    int processCarry(ListNode* node) {
        // Base case: end of list, return 1 to add to the last digit
        if (!node) {
            return 1;
        }
        
        // Recursive step: process the rest of the list first
        int carry = processCarry(node->next);
        
        // If there is no carry to add, we can stop early or just return 0
        if (carry == 0) return 0;
        
        // Perform addition logic
        int sum = node->val + carry;
        node->val = sum % 10;
        return sum / 10;
    }

    ListNode* plusOne(ListNode* head) {
        int carry = processCarry(head);
        
        // If there is a remaining carry after processing the head
        if (carry > 0) {
            ListNode* newHead = new ListNode(carry);
            newHead->next = head;
            return newHead;
        }
        
        return head;
    }
};

Java Solution for LeetCode 369

java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        int carry = processCarry(head);
        
        // If carry propagates out of the most significant digit
        if (carry > 0) {
            ListNode newHead = new ListNode(carry);
            newHead.next = head;
            return newHead;
        }
        
        return head;
    }
    
    // Recursive helper to handle addition from LSB to MSB
    private int processCarry(ListNode node) {
        if (node == null) {
            return 1; // Initial +1 at the end of the list
        }
        
        int carry = processCarry(node.next);
        
        // Optimization: if carry is 0, no need to update current node
        if (carry == 0) return 0;
        
        int sum = node.val + carry;
        node.val = sum % 10;
        return sum / 10;
    }
}

Python Solution for LeetCode 369

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: ListNode) -> ListNode:
        
        def process_carry(node):
            # Base case: if we passed the last node, return 1 (the value to add)
            if not node:
                return 1
            
            # Recurse to the end
            carry = process_carry(node.next)
            
            # If no carry coming back, return 0 immediately
            if carry == 0:
                return 0
            
            # Update current node
            total = node.val + carry
            node.val = total % 10
            return total // 10
        
        # Start the recursion from head
        carry = process_carry(head)
        
        # If the head itself generated a carry (e.g., 99 -> 100)
        if carry:
            new_head = ListNode(carry)
            new_head.next = head
            return new_head
            
        return head