Reverse Linked List

Problem Description

Given the head of a singly linked list, reverse the list and return the new head.

Examples

Constraints

• The number of nodes in the list is in the range [0, 5000].
• -5000 ≤ Node.val ≤ 5000

You Need to Save the Next Node Before You Overwrite the Pointer

The reversal is straightforward: for each node, point curr.next at prev instead of forward. The trap is that once you do curr.next = prev, you’ve lost your reference to the rest of the list. Save curr.next to a temp variable before you redirect the pointer. Then advance both prev and curr and repeat.

After the loop, curr is null and prev is pointing at the old last node, which is now the new head.

Solution 1: Iterative (Three Pointers)

Walk the list, reversing each link in place.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;  // save before we overwrite the pointer
            curr.next = prev;           // redirect link backward
            prev = curr;               // advance prev
            curr = next;               // restore curr from saved next
        }
        return prev;
    }
}

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_node = curr.next  # save before we overwrite the pointer
            curr.next = prev       # redirect link backward
            prev = curr            # advance prev
            curr = next_node       # restore curr from saved next
        return prev

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;  // save before we overwrite the pointer
            curr->next = prev;            // redirect link backward
            prev = curr;                  // advance prev
            curr = next;                  // restore curr from saved next
        }
        return prev;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Each node is visited once.
• Space Complexity: O(1). Three pointer variables regardless of list size.

Where it breaks: nothing breaks on a correct implementation, but missing the next = curr.next save causes an infinite loop or null pointer. That’s the one line candidates most often drop under pressure.

Solution 2: Recursive

Recurse to the end, then fix pointers on the way back up.

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next); // recurse to end
        head.next.next = head;  // make the next node point back to current
        head.next = null;       // cut the forward link to avoid a cycle
        return newHead;
    }
}

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)  # recurse to end
        head.next.next = head  # make the next node point back to current
        head.next = None       # cut the forward link to avoid a cycle
        return new_head

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* newHead = reverseList(head->next);  // recurse to end
        head->next->next = head;  // make the next node point back to current
        head->next = nullptr;     // cut the forward link to avoid a cycle
        return newHead;
    }
};

Complexity Analysis:

• Time Complexity: O(n). One recursive call per node.
• Space Complexity: O(n). Call stack depth equals list length.

Where it breaks: on a list of 5000 nodes, this uses O(5000) stack frames. In languages with small stack sizes or strict limits, this risks a stack overflow. The iterative version is always the safer production choice.

Why Prefer Iterative Over Recursive Here?

The recursive version is elegant but uses O(n) stack space. The iterative version uses O(1) space and is equally readable once you understand the three-pointer swap. In an interview, starting with iterative and offering recursive as a follow-up (“I could also write this recursively, but the call stack would be O(n)”) demonstrates you’re thinking about space trade-offs.

Common Mistakes

• Forgetting to save curr.next before redirecting the pointer. After curr.next = prev, the rest of the list is unreachable. This must be saved first.
• Returning curr instead of prev at the end. At loop exit, curr is null. prev is the new head.
• Not setting head.next = null in the recursive solution. Without this line, the original head still points forward, creating a cycle between the first and second nodes.

Frequently Asked Questions

Can you reverse a doubly linked list with this approach? Yes, but you’d also need to update the prev pointer of each node in addition to next. The three-pointer iterative pattern still applies.

What if the list has only one node? Both solutions handle it: the iterative loop runs once (or not at all for empty), and the recursive base case catches head.next == null immediately.

Why do interviewers still ask this if it’s considered easy? Because the follow-ups test understanding: reverse in groups of k, reverse only part of the list, detect if a linked list is a palindrome (which requires reversing the second half). The pattern is foundational.

← All Problems