Reverse Linked List — The Pointer Rewiring Problem Every Interview Starts With

Problem Statement#

Given the head of a singly linked list, reverse the list and return the reversed list's head.

Constraints:

• The number of nodes in the list is in the range [0, 5000]
• -5000 <= Node.val <= 5000
• Both iterative and recursive solutions are expected in interviews
• Target time complexity: O(n); target extra space: O(1) iterative, O(n) recursive

Input:  head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Why This Problem Matters#

Reverse Linked List is the absolute entry point for every linked-list section in FAANG interviews. Meta, Amazon, and Google use it not only as a standalone problem but as a sub-routine inside dozens of harder problems: Reorder List, Palindrome Linked List, Reverse Nodes in K-Group, Add Two Numbers II — they all require you to reverse a list or a segment of one. If your reversal is shaky, those harder problems become impossible under interview time pressure.

The deeper reason this problem matters is that it tests whether you understand pointer ownership. In a singly linked list, each node owns exactly one pointer — the pointer to its successor. Reversing the list means making each node point to its predecessor. That description is obvious in English but surprisingly tricky to implement without losing the next reference before you overwrite the current pointer. Interviewers watch whether you reach for the three-pointer pattern immediately or stumble through the logic during the conversation.

The recursive variant additionally tests your understanding of call-stack behavior and the difference between "returning the new head" versus "rewiring the tail." Both versions appear in interviews, and you should be able to explain why both have the same asymptotic time complexity but differ in space usage by O(n) versus O(1).

The Core Insight#

Every node in the reversed list must point to the node that was immediately before it in the original list, so you need to rewire curr.next = prev for every node. The catch is that once you do this, you have permanently lost the reference to the original next node — which is exactly the next node you need to process. The three-pointer pattern saves nxt = curr.next before the rewiring happens, then uses that saved reference to advance both prev and curr without losing your place.

Visual Dry Run#

Input: 1 -> 2 -> 3 -> 4 -> 5 -> None

Result: 5 -> 4 -> 3 -> 2 -> 1 -> None

Solution (Optimal)#

class Solution:
    def reverseList(self, head):
        # Iterative three-pointer reversal — O(n) time, O(1) space
        prev = None      # will become the new "next" of each rewired node
        curr = head      # current node being processed
        while curr:
            nxt = curr.next     # save next BEFORE overwriting
            curr.next = prev    # rewire backward
            prev = curr         # advance prev to current
            curr = nxt          # advance curr to saved next
        return prev             # prev is the new head (last non-null node)
 
    def reverseListRecursive(self, head):
        # Recursive — O(n) time, O(n) stack space
        if not head or not head.next:
            return head                          # base case
        new_head = self.reverseListRecursive(head.next)
        head.next.next = head                    # tail of reversed sublist points back
        head.next = None                         # cut head's forward link
        return new_head                          # bubble new head up unchanged

// Iterative three-pointer reversal — O(n) time, O(1) space
var reverseList = function(head) {
    let prev = null;        // tracks the previous node (becomes new tail's next)
    let curr = head;        // tracks the current node being processed
    while (curr) {
        const nxt = curr.next;   // save next BEFORE overwriting
        curr.next = prev;        // rewire backward
        prev = curr;             // advance prev
        curr = nxt;              // advance curr
    }
    return prev;            // new head is the last visited node
};
 
// Recursive — O(n) time, O(n) stack space
var reverseListRecursive = function(head) {
    if (!head || !head.next) return head;        // base case
    const newHead = reverseListRecursive(head.next);
    head.next.next = head;                       // make tail point back
    head.next = null;                            // cut forward link
    return newHead;                              // pass new head up
};

Time: O(n) — every node is visited and rewired exactly once Space: O(1) iterative, O(n) recursive (call stack)

Common Mistakes#

• Overwriting curr.next before saving nxt — you permanently lose the rest of the list
• Returning curr instead of prev — curr is None at loop termination, so you return an empty list
• Forgetting to initialize prev = None — the new tail then points at a stale node and you create a cycle
• Recursive base case if not head only — single-node case crashes when accessing head.next.next
• Forgetting head.next = None in the recursive approach — you create a cycle between head and head.next

Interview Tips#

• Always present the iterative solution first — it has O(1) space and is the expected default
• State the invariant clearly: "after each iteration, prev points at the new head of the reversed prefix"
• When the interviewer asks about the recursive version, mention the O(n) stack space tradeoff up front
• Draw the four pointer states (init, mid-loop, post-rewire, post-advance) on the whiteboard before coding
• Mention that this same loop is the inner subroutine for Reverse Nodes in K-Group and Reverse Linked List II

Follow-up Questions#

• Can you reverse a linked list without extra space? Hint: yes — the iterative version uses only three pointer variables.
• What if the list has a cycle? Hint: the iterative loop never terminates because curr never becomes None.
• Can you reverse only a portion of the list, given two indices? Hint: that is LeetCode 92, same three-pointer core wrapped in segment boundaries.
• How does this compare to reversing an array? Hint: arrays use two-pointer swap from both ends, lists rewire in a single forward pass.
• How would you reverse a doubly linked list? Hint: swap each node's prev and next, then return the original tail as the new head.

Key Takeaways#

• Save nxt before rewiring, return prev not curr — those two rules cover 95% of the bugs
• The iterative three-pointer pattern is the atomic building block of every advanced linked-list problem
• Recursive reversal trades O(n) stack space for code elegance — interview default should be iterative
• The recursive approach must do two things at the unwind: head.next.next = head and head.next = None
• Once this muscle memory is wired, partial reversal, k-group reversal, and palindrome checking all become variations
• The same prev/curr/nxt template adapts to reversing between two indices by saving the boundary nodes
• Interviewers grade reversal as "must produce in 5 minutes flat" — drill it until it is reflexive