Code Implementation

# 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:
        # Helper function to reverse a linked list
        def reverse(node):
            prev = None
            while node:
                next_node = node.next
                node.next = prev
                prev = node
                node = next_node
            return prev

        # Reverse the list
        head = reverse(head)
        curr = head
        carry = 1

        # Add one to the reversed list
        while curr and carry:
            curr.val += carry
            if curr.val < 10:
                carry = 0
            else:
                curr.val = 0
                carry = 1
            if carry and not curr.next:
                curr.next = ListNode(0)
            curr = curr.next

        # Reverse it back
        return reverse(head)
      

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        while (head) {
            ListNode* next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    ListNode* plusOne(ListNode* head) {
        head = reverse(head);
        ListNode* curr = head;
        int carry = 1;
        while (curr && carry) {
            curr->val += carry;
            if (curr->val < 10) {
                carry = 0;
            } else {
                curr->val = 0;
                carry = 1;
            }
            if (carry && curr->next == nullptr) {
                curr->next = new ListNode(0);
            }
            curr = curr->next;
        }
        return reverse(head);
    }
};
      

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    public ListNode plusOne(ListNode head) {
        head = reverse(head);
        ListNode curr = head;
        int carry = 1;
        while (curr != null && carry != 0) {
            curr.val += carry;
            if (curr.val < 10) {
                carry = 0;
            } else {
                curr.val = 0;
                carry = 1;
            }
            if (carry != 0 && curr.next == null) {
                curr.next = new ListNode(0);
            }
            curr = curr.next;
        }
        return reverse(head);
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var plusOne = function(head) {
    // Helper to reverse a linked list
    function reverse(node) {
        let prev = null;
        while (node) {
            let next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }
    head = reverse(head);
    let curr = head;
    let carry = 1;
    while (curr && carry) {
        curr.val += carry;
        if (curr.val < 10) {
            carry = 0;
        } else {
            curr.val = 0;
            carry = 1;
        }
        if (carry && !curr.next) {
            curr.next = new ListNode(0);
        }
        curr = curr.next;
    }
    return reverse(head);
};
      

Problem Description

You are given the head of a non-empty singly linked list representing a non-negative integer, where each node contains a single digit. The most significant digit is at the head of the list, and each node's value is in the range 0-9.

Your task is to add one to this number and return the head of the resulting linked list.

• You must not modify the input list except as needed to produce the result.
• There is exactly one valid output for each input.
• Each node can only be used once and must not be reused.

For example, if the input list is 1 -> 2 -> 3, the output should be 1 -> 2 -> 4.

Thought Process

At first glance, the problem seems similar to adding one to an integer. However, since the number is represented as a singly linked list (with the most significant digit at the head), we cannot easily access the least significant digit (the tail) directly.

A brute-force approach might be to reverse the linked list so that we can process the number from the least significant digit, just as we would if it were an array or a string. Alternatively, we could use recursion to reach the end of the list and then propagate the carry backwards as we unwind the recursion.

We also need to consider the edge case where adding one causes a carry that creates a new digit at the front (for example, 9 -> 9 -> 9 becomes 1 -> 0 -> 0 -> 0).

The optimized solution should minimize extra space and avoid unnecessary traversals. By reversing the list, we can perform the addition in a single pass, then reverse it back.

Solution Approach

The optimal way to solve this problem is to reverse the linked list, add one as we traverse from the new head (original tail), and then reverse the list back to restore the original order.

1. Reverse the linked list: This allows us to process the number from the least significant digit, just like we would do with an array from right to left.
2. Add one to the number: Start from the head of the reversed list, add one, and handle the carry as we move through each node. If a node becomes 10, set it to 0 and continue the carry to the next node.
3. Handle extra carry: If, after processing all nodes, there is still a carry left, create a new node with value 1 at the end (which will become the new head after reversing back).
4. Reverse the list again: Restore the original order of digits, now reflecting the incremented value.

This approach is efficient because each operation (reversing and traversing) is linear in time and does not require extra space proportional to the size of the list (other than a few pointers).

Example Walkthrough

Let's take the input 2 -> 4 -> 9.

1. Reverse the list: Now we have 9 -> 4 -> 2.
2. Add one:
   • Start at 9: 9 + 1 = 10. Set current node to 0, carry = 1.
   • Move to 4: 4 + 1 = 5. Set current node to 5, carry = 0.
   • Since carry is 0, we stop processing further nodes.
3. Reverse back: The list is now 2 -> 5 -> 0.

Thus, 2 -> 4 -> 9 plus one becomes 2 -> 5 -> 0.

For an edge case like 9 -> 9 -> 9:

• Reverse: 9 -> 9 -> 9
• Add one: Each node becomes 0 with carry=1, and a new node with value 1 is added at the end.
• Reverse back: 1 -> 0 -> 0 -> 0

Time and Space Complexity

Brute-force approach (using recursion): Each recursive call adds to the call stack, so space complexity is O(n), where n is the length of the list.

Optimized approach (reversal):

• Time complexity: O(n) — We traverse the list three times (reverse, add, reverse), each taking O(n) time.
• Space complexity: O(1) — We only use a constant number of pointers, and do not use extra space proportional to n.

Summary

The Plus One Linked List problem is a great example of adapting number manipulation algorithms to linked data structures. By reversing the list, we enable efficient addition from the least significant digit. The solution is elegant because it avoids recursion, uses only constant extra space, and handles carries in a single traversal. This approach is both efficient and easy to understand, making it a robust solution for similar linked list arithmetic problems.