LeetCode 369: Plus One Linked List Solution in Python – A Step-by-Step Guide

What Is LeetCode 369: Plus One Linked List?

LeetCode 369: Plus One Linked List provides a singly linked list where each node’s value (0-9) represents a digit in a number, most significant digit first. Your task is to add 1 to this number and return the resulting linked list, handling carry-overs as needed. It’s a linked list problem with a numeric twist!

Problem Statement

• Input:
• head: Head node of a singly linked list (ListNode class).
• Output: ListNode - Head of the linked list after adding 1.
• Rules:
• Each node’s value is a digit (0-9).
• List represents a number with most significant digit at head.
• Handle carry-over (e.g., 9→9→9 + 1 = 1→0→0→0).

Constraints

• Number of nodes: 1 to 10⁴.
• Node values: 0 to 9.
• No leading zeros in input (except for 0 itself).

Examples

• Input: head = [1,2,3]
• Output: [1,2,4]
• 123 + 1 = 124.
• Input: head = [9,9,9]
• Output: [1,0,0,0]
• 999 + 1 = 1000 (carry propagates, new digit added).
• Input: head = [0]
• Output: [1]
• 0 + 1 = 1.

These show the carry challenge—let’s solve it!

Understanding the Problem: Adding One to a Linked List

To tackle LeetCode 369 in Python, we need to: 1. Add 1 to the number represented by the linked list. 2. Handle carry-overs from right to left (least to most significant). 3. Adjust the list structure if a new digit is needed (e.g., 999 → 1000).

A naive approach might convert to an integer and back, but that risks overflow. Instead, we’ll use:

• Best Solution: Two-pass reversal—O(n) time, O(1) space—fast and space-efficient.
• Alternative Solution: Recursion—O(n) time, O(n) space—intuitive but uses stack.

Let’s increment with the best solution!

Best Solution: Two-Pass Reversal

Why This Is the Best Solution

The two-pass reversal approach runs in O(n) time with O(1) extra space by:

• First pass: Reverse the list to process least significant digit first.
• Second pass: Add 1, handle carry, reverse back.

It’s the most efficient—avoiding recursion’s stack overhead while keeping operations in-place!

How It Works

Think of it like flipping the list:

• Reverse: Flip the list (e.g., 1→2→3 → 3→2→1).
• Add One: Start at head (now least significant), add 1, propagate carry, adjust structure.
• Reverse Back: Restore original order (e.g., 4→2→1 → 1→2→4).
• Result: Return new head.

It’s like doing addition on paper, but with linked list gymnastics!

Step-by-Step Example

For head = [1,2,3]:

• Original: 1→2→3 (123).
• Pass 1: Reverse: 3→2→1.
• Pass 2: Add 1:
• 3 + 1 = 4, carry=0, 4→2→1.
• 2 + 0 = 2, 4→2→1.
• 1 + 0 = 1, 4→2→1.
• Reverse Back: 1→2→4 (124).
• Result: [1,2,4].

For head = [9,9,9]:

• Reverse: 9→9→9.
• Add 1:
• 9 + 1 = 10, carry=1, 0→9→9.
• 9 + 1 = 10, carry=1, 0→0→9.
• 9 + 1 = 10, carry=1, 0→0→0.
• Carry=1, new node 1, 0→0→0→1.
• Reverse Back: 1→0→0→0 (1000).
• Result: [1,0,0,0].

Code with Explanation

Here’s the Python code using two-pass reversal:

Copy codeclass Solution:
    def plusOne(self, head: ListNode) -> ListNode:
        # Helper to reverse linked list
        def reverse(node):
            prev = None
            curr = node
            while curr:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev

        # Pass 1: Reverse the list
        head = reverse(head)

        # Pass 2: Add 1 and handle carry
        curr = head
        carry = 1
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        while curr:
            total = curr.val + carry
            curr.val = total % 10
            carry = total // 10
            prev = curr
            curr = curr.next

        # If carry remains, add new node
        if carry:
            prev.next = ListNode(carry)

        # Reverse back to original order
        return reverse(head)

Explanation

• Lines 3-11: reverse:
• Reverse list by flipping pointers—O(n) time, O(1) space.
• Line 14: First pass reverses list (e.g., 1→2→3 → 3→2→1).
• Lines 16-26: Second pass:
• Start with carry=1 (adding 1).
• Use dummy to handle potential new head.
• For each node: Add carry, update value (total % 10), set new carry (total // 10).
• Track prev for carry case.
• Lines 28-29: If carry=1 after last node, append new node (e.g., 0→0→0→1).
• Line 32: Reverse back to original order—O(n).
• Time: O(n)—three O(n) passes (reverse, add, reverse).
• Space: O(1)—only pointers, no extra structure.

This is like flipping the number, adding, and flipping back—neat and efficient!

Alternative Solution: Recursion

Why an Alternative Approach?

The recursive solution also runs in O(n) time but uses O(n) space due to the call stack. It’s more intuitive—traverse to the end, add 1, and propagate carry backward—great for understanding the carry process!

How It Works

• Recurse: Go to the last node, add 1, return carry.
• Propagate: Move up, apply carry, update nodes.
• Result: Adjust head if carry remains.

Step-by-Step Example

For head = [1,2,3]:

• Recurse:
• 3: 3+1=4, carry=0, return 0.
• 2: 2+0=2, carry=0, return 0.
• 1: 1+0=1, carry=0, return 0.
• Result: 1→2→4.

For head = [9,9,9]:

• Recurse:
• 9: 9+1=10, val=0, carry=1, return 1.
• 9: 9+1=10, val=0, carry=1, return 1.
• 9: 9+1=10, val=0, carry=1, return 1.
• Head: Carry=1, new node 1→0→0→0.
• Result: [1,0,0,0].

Code with Explanation

Copy codeclass Solution:
    def plusOne(self, head: ListNode) -> ListNode:
        # Recursive helper to add 1 and return carry
        def add_one(node):
            if not node:
                return 1  # Base case: add 1 at end

            # Recurse to next node
            carry = add_one(node.next)
            total = node.val + carry
            node.val = total % 10
            return total // 10

        # Add 1 starting from head
        carry = add_one(head)

        # If carry remains, add new node at head
        if carry:
            new_head = ListNode(carry)
            new_head.next = head
            return new_head

        return head

Explanation

• Lines 3-11: add_one:
• Base case: Null node, return 1 (start adding).
• Recurse to next, get carry.
• Update current node with total % 10, return total // 10.
• Line 14: Start recursion from head.
• Lines 16-19: If carry=1 after recursion, prepend new node.
• Time: O(n)—single pass via recursion.
• Space: O(n)—recursion stack.

It’s like adding from the end up—carry flows naturally!

Comparing the Two Solutions

• Two-Pass Reversal (Best):
• Time: O(n)—three linear passes.
• Space: O(1)—in-place.
• Pros: Fast, space-efficient.
• Cons: More steps (reversals).
• Recursion (Alternative):
• Time: O(n)—single pass.
• Space: O(n)—stack.
• Pros: Intuitive carry handling.
• Cons: Stack overhead.

Reversal wins for space efficiency!

Additional Examples and Edge Cases

• [1]: [2].
• [9]: [1,0].
• Long list: Both scale linearly.

Both handle these, reversal uses less space.

Complexity Breakdown

• Reversal:
• Time: O(n).
• Space: O(1).
• Recursion:
• Time: O(n).
• Space: O(n).

Reversal excels for space.

Key Takeaways

• Reversal: Flip and add—fast and lean!
• Recursion: Carry up—clear and natural!
• Lists: Structure meets math.
• Python Tip: Pointers rock—see [Python Basics](/python/basics).

Final Thoughts: Increment That List

LeetCode 369: Plus One Linked List in Python is a list-arithmetic challenge. Two-pass reversal is the efficiency champ, while recursion builds intuition. Want more? Try LeetCode 2: Add Two Numbers or LeetCode 206: Reverse Linked List. Ready to add? Visit Solve LeetCode 369 on LeetCode (premium) and increment that list today!