Skip to content
C Codeloom
DSA

LeetCode Reverse Linked List: Iterative and Recursive

Walk through LeetCode 206 Reverse Linked List with iterative pointer flipping and a clean recursive solution, plus complexity and interview talking points.

·5 min read · By Yash Kesharwani
Intermediate 9 min read

What you'll learn

  • ✓Why the iterative reversal uses three pointers
  • ✓How to derive the recursive solution from first principles
  • ✓When to prefer iterative over recursive in interviews
  • ✓How to dry-run the algorithm without losing track of pointers
  • ✓How to discuss tradeoffs and edge cases clearly

Prerequisites

  • •Read [Linked Lists Introduction](/blog/linked-lists-introduction) for node structure basics
  • •Read [Linked Lists Common Operations](/blog/linked-lists-common-operations) for pointer manipulation patterns

LeetCode 206 Reverse Linked List is rated Easy, but it is one of the most frequently asked warm-up questions at every level of interview. It is also the foundation for harder problems like Reverse Nodes in k-Group and Palindrome Linked List. If you can explain both the iterative and recursive versions cleanly, you have a strong signal of comfort with pointer manipulation.

In this walkthrough we will build up both solutions, dry-run them on a small list, and discuss the edge cases interviewers like to probe.

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.

Brute Force

A naive approach is to walk the list once, copy each value into an array, then build a new linked list from the reversed array. This works but allocates new nodes and uses extra memory.

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

def reverse_list_brute(head):
    values = []
    cur = head
    while cur:
        values.append(cur.val)
        cur = cur.next

    dummy = ListNode()
    tail = dummy
    for v in reversed(values):
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

This is O(n) time and O(n) extra space. Interviewers will push you to do it in place.

Optimal Solution

The optimal approach reverses the next pointers in a single pass using three pointers: prev, curr, and a saved next_node.

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

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.

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

Both run in linear time. The iterative version uses constant extra space; the recursive version uses O(n) stack space.

Walk Through an 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. List looks like 1 -> None and 2 -> 3 -> None.

Iteration 2: save next_node = 3, set 2.next = 1, advance prev = 2, curr = 3. Reversed chunk: 2 -> 1 -> None.

Iteration 3: save next_node = None, set 3.next = 2, advance prev = 3, curr = None. Reversed chunk: 3 -> 2 -> 1 -> None.

Loop exits and we return prev, which points to node 3, the new head.

Edge Cases

  • Empty list: head is None. The loop never executes and we return None.
  • Single node: head.next is already None. The loop runs once, sets head.next = None (no-op), and returns the same node.
  • Two-node list: covers the smallest non-trivial swap and catches off-by-one mistakes.
  • Cycles: the problem assumes no cycles. If a cycle existed, the iterative loop would never terminate, so mention detection if asked.

Complexity Analysis

Iterative:

  • Time: O(n) where n is the number of nodes. Each node is visited once.
  • Space: O(1) auxiliary. We only use three pointers.

Recursive:

  • Time: O(n).
  • Space: O(n) due to the recursion stack. For very large lists this can hit Python recursion limits.

How to Explain It in an Interview

Lead with 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 are: save the next pointer so we do not lose the rest of the list, flip the current node to point backward, and advance both pointers. That sentence usually convinces the interviewer you understand it without needing to draw.

For the recursive version, explain that you recurse to the end first, then on the way back you flip pointers so that head.next.next = head. Setting head.next = None is critical, otherwise the original head would still point forward and you would create a cycle.

If you have time, mention you would prefer the iterative version in production because it avoids stack-overflow risk on long lists.

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

Wrap up

Reversing a linked list is short to write but rich in fundamentals: pointer hygiene, base cases, in-place mutation, and choosing between iteration and recursion. 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 to a sublist.