Reverse Linked List — Iterative and Recursive

Reverse Linked List is rated Easy, but it is one of the most frequently asked warm-up questions and the foundation for harder problems like Reverse Nodes in k-Group and Palindrome Linked List.

The Problem

Given the head of a singly linked list, return the head of the list after reversing it in place.

Example:

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

Constraints typically state that the number of nodes is between 0 and 5000 and each node value fits in a 32-bit integer.

Intuition

A brute force walks the list copying values into an array, then builds a new list from the reversed array. O(n) time and O(n) extra space — interviewers will push you to do it in place.

The optimal idea reverses the next pointers in a single pass using three pointers: prev, curr, and a saved next_node. The invariant: at every step, prev points to the head of the already-reversed prefix, and curr points to the next node to process. The three lines inside the loop save the next pointer, flip the current node backward, and advance both pointers.

The recursive version mirrors the same logic. The base case returns when we hit the tail, then each frame flips the link on the way back up. Setting head.next = None after head.next.next = head is critical to avoid a cycle.

Explanation with Example

Start with 1 -> 2 -> 3 -> None and the iterative method.

Initial: prev = None, curr = 1.

Iteration 1: save next_node = 2, set 1.next = None, advance prev = 1, curr = 2.

Iteration 2: save next_node = 3, set 2.next = 1, advance prev = 2, curr = 3.

Iteration 3: save next_node = None, set 3.next = 2, advance prev = 3, curr = None. Loop exits.

Return prev, which now points to node 3, the new head.

start:    None    1 -> 2 -> 3 -> None
        prev   curr

iter 1:   None <- 1    2 -> 3 -> None
               prev  curr

iter 2:   None <- 1 <- 2    3 -> None
                    prev  curr

iter 3:   None <- 1 <- 2 <- 3    None
                          prev curr

return prev -> 3 -> 2 -> 1 -> None

Code

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

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

class ListNode {
    int val; ListNode next;
    ListNode(int val) { this.val = val; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

struct ListNode {
    int val; ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    ListNode* reverseListRecursive(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* newHead = reverseListRecursive(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

Edge Cases

• Empty list: head is None. The loop never executes and we return None.
• Single node: head.next is already None. Loop runs once, no-op flip, returns the same node.
• Two-node list: smallest non-trivial swap, catches off-by-one mistakes.
• Cycles: the problem assumes none. If one existed, iteration would never terminate.

Complexity Analysis

Iterative:

• Time: O(n).
• Space: O(1) auxiliary.

Recursive:

• Time: O(n).
• Space: O(n) for the recursion stack. Hits Python recursion limits on long lists.

How to Explain It in an Interview

Lead with the invariant: prev points to the reversed prefix, curr to the next to process. The three lines save, flip, and advance. For the recursive version, explain that you recurse to the tail first, then flip pointers on the way back. Setting head.next = None is essential — otherwise you create a cycle. Prefer the iterative version in production to avoid stack-overflow risk.

Related Problems

• Reverse Linked List II, which reverses only a sublist.
• Reverse Nodes in k-Group, which reverses chunks of size k.
• Palindrome Linked List, which uses reversal on the second half.
• Merge Two Sorted Lists for more dummy-head pointer practice.

Wrap up

Practice both versions until you can write either from memory in under two minutes. Then revisit Linked Lists Common Operations and try Reverse Linked List II to extend the pattern.