LeetCode 369 - Plus One Linked List

LeetCode Problem 369

Difficulty: 🟡 Medium
Topics: Linked List, Math

Solution

Problem Understanding

The problem requires us to add one to a non-negative integer that is represented as a singly-linked list. Each node in the list contains a single digit, and the head of the list corresponds to the most significant digit. Essentially, the linked list [1,2,3] represents the integer 123, and adding one should transform it into [1,2,4], representing 124.

The input is guaranteed to be a valid non-negative integer with no leading zeros, except for the special case where the number is zero ([0]). The number of nodes is between 1 and 100, which implies that the solution must handle moderately sized lists efficiently. Each node’s value is between 0 and 9.

Important edge cases include a linked list ending in one or more 9s (e.g., [1,2,9] or [9,9,9]), which will require carrying over to the preceding digits, possibly increasing the length of the list. The problem guarantees a valid input, so we do not need to handle empty lists or negative numbers.

The task is complicated slightly by the fact that the most significant digit is at the head, meaning we cannot simply traverse and add from the front like we would in an array without a reverse or stack-based approach.

Approaches

A brute-force approach would be to convert the linked list to an integer, add one, and then reconstruct the linked list. This works because the integer representation allows simple arithmetic, and it guarantees correctness. However, for very large lists (close to 100 digits), converting to an integer may exceed standard integer types in some languages, and repeated string manipulation could be inefficient.

The optimal approach leverages the fact that addition with carry propagates from the least significant digit to the most significant digit. Since the list is singly-linked, the simplest way to process from least significant to most significant is to reverse the linked list, perform the addition while propagating the carry, and then reverse the list back. An alternative without reversing is a recursive approach, where the recursion stack simulates traversing the list in reverse.

The key insight is that we only need to track a carry as we add one, and once the carry is zero, we can terminate early. For cases where all digits are 9, we may need to create a new head node with value 1 and append zeros for the rest.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Convert list to integer or string, add one, reconstruct list. Simple but not elegant; may cause integer overflow in some languages.
Optimal	O(n)	O(1)	Reverse list, add one with carry, reverse back. Handles carry propagation efficiently without extra integer conversion.

Algorithm Walkthrough

1. Reverse the linked list so that the least significant digit is at the head. This allows us to traverse the list in the natural order of addition with carry.
2. Initialize a carry variable with value 1 because we are adding one to the number.
3. Traverse the reversed list node by node. For each node, add the carry to the node’s value. Update the node’s value to sum % 10 and set carry to sum // 10. This handles cases where the sum exceeds 9 and needs to propagate to the next digit.
4. If, after traversing all nodes, the carry is still 1, create a new node with value 1 and append it to the list. This handles cases like [9,9,9].
5. Reverse the list again to restore the original order, so the most significant digit is back at the head.

Why it works: By reversing the list, we convert the problem into a standard addition-from-least-significant-digit problem, where carry propagation is straightforward. The algorithm ensures that each digit is correctly updated, and the extra node ensures correctness when the number of digits increases.

Python Solution

# 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: ListNode) -> ListNode:
            prev = None
            current = node
            while current:
                next_node = current.next
                current.next = prev
                prev = current
                current = next_node
            return prev
        
        head = reverse(head)
        current = head
        carry = 1
        
        while current:
            total = current.val + carry
            current.val = total % 10
            carry = total // 10
            if carry == 0:
                break
            if current.next is None and carry:
                current.next = ListNode(carry)
                carry = 0
            current = current.next
        
        head = reverse(head)
        return head

This Python solution first reverses the linked list to process the least significant digits first. The while loop handles addition and carry propagation. If there is still a carry after reaching the end of the list, a new node is appended. Finally, the list is reversed again to restore the original order.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func plusOne(head *ListNode) *ListNode {
    // Helper function to reverse a linked list
    var reverse func(node *ListNode) *ListNode
    reverse = func(node *ListNode) *ListNode {
        var prev *ListNode
        current := node
        for current != nil {
            next := current.Next
            current.Next = prev
            prev = current
            current = next
        }
        return prev
    }

    head = reverse(head)
    current := head
    carry := 1

    for current != nil {
        total := current.Val + carry
        current.Val = total % 10
        carry = total / 10
        if carry == 0 {
            break
        }
        if current.Next == nil && carry > 0 {
            current.Next = &ListNode{Val: carry}
            carry = 0
        }
        current = current.Next
    }

    head = reverse(head)
    return head
}

In Go, the logic is nearly identical. Go requires explicit handling of pointers and nil checks. Unlike Python, we use integer division with / and modulus % operators and create new nodes with &ListNode{Val: carry} when needed.

Worked Examples

Example 1: [1,2,3]

Reverse: [3,2,1]

Initial carry = 1

Node Val	Add carry	New Val	Carry
3	3+1	4	0

No more carry, stop. Reverse back: [1,2,4].

Example 2: [0]

Reverse: [0]

Initial carry = 1

Node Val	Add carry	New Val	Carry
0	0+1	1	0

No more carry, stop. Reverse back: [1].

Example 3: [9,9,9]

Reverse: [9,9,9] → [9,9,9]

Initial carry = 1

Node Val	Add carry	New Val	Carry
9	9+1	0	1
9	9+1	0	1
9	9+1	0	1

End of list, create new node with value 1. Reverse back: [1,0,0,0].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Reversing the list twice and traversing it once for addition is linear in the number of nodes.
Space	O(1)	We only use a constant number of variables (prev, current, carry) and modify the list in-place.

The algorithm avoids extra memory allocation beyond the occasional new node for carry propagation. Each node is visited a constant number of times, giving linear runtime.

Test Cases

# test cases
def list_to_nodes(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

def nodes_to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

sol = Solution()

# Provided examples
assert nodes_to_list(sol.plusOne(list_to_nodes([1,2,3]))) == [1,2,4]  # normal addition
assert nodes_to_list(sol.plusOne(list_to_nodes([0]))) == [1]  # single zero

# Edge cases
assert nodes_to_list(sol.plusOne(list_to_nodes([9,9,9]))) == [1,0,0,0]  # all 9s
assert nodes_to_list(sol.plusOne(list_to_nodes([1,9,9]))) == [2,0,0]  # carry through middle