LeetCode 206: Reverse Linked List Solution in Python Explained

Problem Statement

In LeetCode 206: Reverse Linked List, you’re given:

• head: The head node of a singly linked list.
• Your task is to return the head of the reversed list.

Each node has a val (value) and a next pointer to the next node or None. For example, 1 → 2 → 3 becomes 3 → 2 → 1. This differs from string mapping in LeetCode 205: Isomorphic Strings, focusing instead on pointer redirection in a linked structure.

Constraints

• Number of nodes: 0 ≤ n ≤ 5000.
• Node values: -5000 ≤ val ≤ 5000.

Examples

Let’s see some cases (list notation for clarity):

Copy codeInput: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation: Reverse the list from 1 → 2 → 3 → 4 → 5 to 5 → 4 → 3 → 2 → 1.

Copy codeInput: head = []
Output: []
Explanation: Empty list remains empty.

Copy codeInput: head = [1]
Output: [1]
Explanation: Single node is already "reversed."

These examples show we’re redirecting pointers to reverse the order.

Understanding the Problem

How do we solve LeetCode 206: Reverse Linked List in Python? For 1 → 2 → 3 → 4 → 5, we need 5 → 4 → 3 → 2 → 1. A naive approach might create a new list, but that’s unnecessary—we can reverse the links in place. This isn’t a prime counting problem like LeetCode 204: Count Primes; it’s about pointer manipulation. We’ll use: 1. Iterative with Three Pointers: O(n) time, O(1) space—our best solution. 2. Recursive Approach: O(n) time, O(n) space—an alternative.

Let’s explore the best solution.

Best Solution: Iterative with Three Pointers Approach

Explanation

The Iterative with Three Pointers approach uses three pointers to reverse links:

• prev: Points to the previous node (starts as None).
• curr: Points to the current node (starts at head).
• next_temp: Temporarily stores the next node before we overwrite curr.next.
• For each node:
• Save the next node.
• Reverse the link (curr.next = prev).
• Move prev and curr forward.

This runs in O(n) time (one pass through the list) and O(1) space (just three pointers), making it efficient and intuitive—our best solution.

For [1,2,3], it flips links step-by-step to [3,2,1].

Step-by-Step Example

Example 1: head = [1,2,3,4,5]

Goal: Return [5,4,3,2,1].

• Step 1: Initialize.
• prev = None, curr = 1, next_temp = None.
• Step 2: Iterate.
• curr = 1:
• next_temp = 2, 1.next = None, prev = 1, curr = 2.
• List: 1 (detached), 2 → 3 → 4 → 5.
• curr = 2:
• next_temp = 3, 2.next = 1, prev = 2, curr = 3.
• List: 2 → 1, 3 → 4 → 5.
• curr = 3:
• next_temp = 4, 3.next = 2, prev = 3, curr = 4.
• List: 3 → 2 → 1, 4 → 5.
• curr = 4:
• next_temp = 5, 4.next = 3, prev = 4, curr = 5.
• List: 4 → 3 → 2 → 1, 5.
• curr = 5:
• next_temp = None, 5.next = 4, prev = 5, curr = None.
• List: 5 → 4 → 3 → 2 → 1.
• Step 3: Finish.
• Return prev (new head = 5).
• Output: [5,4,3,2,1].

Example 2: head = [1,2]

Goal: Return [2,1].

• Step 1: prev = None, curr = 1.
• Step 2:
• curr = 1: next_temp = 2, 1.next = None, prev = 1, curr = 2.
• curr = 2: next_temp = None, 2.next = 1, prev = 2, curr = None.
• Output: 2 → 1, return 2.

How the Code Works (Iterative with Three Pointers) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown (assuming a ListNode class):

Copy codeclass ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    # Line 1: Initialize pointers
    prev = None
    # Previous node starts as None (e.g., None)
    curr = head
    # Current node starts at head (e.g., 1)

    # Line 2: Iterate through the list
    while curr:
        # Continue until end (e.g., curr != None)
        next_temp = curr.next
        # Save next node (e.g., 2)
        curr.next = prev
        # Reverse link (e.g., 1 → None)
        prev = curr
        # Move prev forward (e.g., prev = 1)
        curr = next_temp
        # Move curr forward (e.g., curr = 2)

    # Line 3: Return new head
    return prev
    # New head is last non-None prev (e.g., 5)

This solution is straightforward and memory-efficient.

Alternative: Recursive Approach

Explanation

The Recursive Approach reverses the list by:

• Base case: If head is None or head.next is None, return head.
• Recursively reverse the rest of the list.
• Adjust pointers to flip the current link.

It’s O(n) time (one pass) and O(n) space (recursion stack), offering an elegant but less space-efficient alternative.

Step-by-Step Example

For [1,2,3]:

• head = 1: Recurse on 2 → 3.
• head = 2: Recurse on 3.
• head = 3: Return 3.
• 2.next = 3: 3.next = 2, 2.next = None, return 3.
• 1.next = 2: 2.next = 1, 1.next = None, return 3.
• Output: 3 → 2 → 1.

How the Code Works (Recursive)

Copy codedef reverseListRecursive(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    new_head = reverseListRecursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

Complexity

• Iterative with Three Pointers:
• Time: O(n) – one pass.
• Space: O(1) – three pointers.
• Recursive Approach:
• Time: O(n) – one pass.
• Space: O(n) – recursion stack.

Efficiency Notes

Iterative with Three Pointers is our best solution with O(1) space and simplicity. Recursive is elegant but uses O(n) space, less ideal for large lists.

Key Insights

• Pointers: Reverse links in place.
• Iterative: Step-by-step reversal.
• Recursive: Bottom-up rebuilding.

Additional Example

For [1,2]:

• Iterative: 2 → 1.
• Recursive: Same result.

Edge Cases

• Empty list: [] → [].
• Single node: [1] → [1].
• Two nodes: [1,2] → [2,1].

Both handle these perfectly.

Final Thoughts

LeetCode 206: Reverse Linked List in Python is a foundational linked list challenge. Iterative with Three Pointers excels in efficiency, while Recursive offers elegance. Want more? Try LeetCode 21: Merge Two Sorted Lists or LeetCode 234: Palindrome Linked List. Test your skills—Solve LeetCode 206 on LeetCode with [1,2,3,4,5] (expecting [5,4,3,2,1])—reverse that list today!