Reverse a Linked List: Iterative and Recursive, Step by Step

Reversing a linked list is the smallest problem that tests whether you can manipulate pointers without losing track of them. The code is five lines. Getting those five lines in the right order is the whole exercise, because one assignment in the wrong place disconnects the rest of the list, and nothing will warn you: the nodes are still in memory, just unreachable.

The problem it solves

Given the head of a singly linked list 1 → 2 → 3 → None, return the head of 3 → 2 → 1 → None. Reuse the existing nodes; do not allocate a new list.

The reversal also appears as a building block inside larger problems: checking whether a list is a palindrome (reverse the second half and compare), reversing the nodes in groups of k, or adding two numbers stored most-significant digit first. Every one of them relies on the same three-pointer loop, so it pays to be able to write it without thinking.

The intuition

Reversing a list does not move any node. It turns every arrow around: the node that pointed at 2 must now point at whatever came before it. So walk the list once and, at each node, flip its next to face backwards.

The catch is that the arrow you are about to flip is the only way to reach the rest of the list. Hence three pointers:

• prev — the already reversed part, initially None.
• node — the node being flipped.
• nxt — the rest of the list, saved before the flip.

Each step is: save node.next in nxt, point node.next at prev, then slide both prev and node one step forward. When node becomes None, prev is the old tail, which is the new head.

Watch it run

The animation reverses the lesson's 1 → 2 → 3. An extra ∅ column on the left is where prev starts, so flipping the first link is visible as an arrow that now points at nothing. Watch the order in each step: nxt jumps ahead first, then the arrow turns, then prev and node slide right. At the end, prev sits on node 3, which is returned as the head.

The code

A minimal node class, two helpers for printing, and the iterative reversal:

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def from_list(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

def reverse(head):
    prev, node = None, head
    while node:
        nxt = node.next          # 1. save the rest of the list
        node.next = prev         # 2. flip this link backwards
        prev, node = node, nxt   # 3. slide both pointers forward
    return prev                  # the old tail is the new head

print(to_list(reverse(from_list([1, 2, 3]))))   # [3, 2, 1]
print(to_list(reverse(from_list([7]))))         # [7]
print(to_list(reverse(None)))                   # []

The recursive version reverses everything after the head first, then hooks the head onto the end. The trick is head.next.next = head: head.next is now the last node of the reversed tail, so pointing it back at head appends head:

def reverse_recursive(head):
    if head is None or head.next is None:
        return head                      # empty or single node: already reversed
    new_head = reverse_recursive(head.next)
    head.next.next = head                # the old second node points back
    head.next = None                     # head is now the tail
    return new_head

print(to_list(reverse_recursive(from_list([1, 2, 3, 4]))))   # [4, 3, 2, 1]

It is elegant and it has a cost the iterative version does not: one stack frame per node. CPython's default recursion limit is 1,000 frames, so a list of a few thousand nodes breaks it:

import sys

print(sys.getrecursionlimit())           # 1000
long_list = from_list(list(range(5000)))
try:
    reverse_recursive(long_list)
except RecursionError:
    print("RecursionError")              # RecursionError
print(to_list(reverse(from_list(list(range(5000)))))[:3])   # [4999, 4998, 4997]

A common follow-up reverses only positions left to right (1-based). Walk to the node before the section, reverse exactly right - left + 1 links with the same loop, then reconnect both ends. A dummy node in front removes the special case where left is 1:

def reverse_between(head, left, right):
    dummy = Node(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next             # node just before the section
    prev, node = None, before.next
    for _ in range(right - left + 1):
        nxt = node.next
        node.next = prev
        prev, node = node, nxt
    before.next.next = node              # old section start -> first node after
    before.next = prev                   # node before -> new section start
    return dummy.next

print(to_list(reverse_between(from_list([1, 2, 3, 4, 5]), 2, 4)))   # [1, 4, 3, 2, 5]

All three against Python's list reversal on 3,000 random lists, including empty lists and sections that cover the whole list:

import random

random.seed(4)
ok = True
for _ in range(3000):
    vals = [random.randint(0, 99) for _ in range(random.randint(0, 20))]
    ok &= to_list(reverse(from_list(vals))) == vals[::-1]
    ok &= to_list(reverse_recursive(from_list(vals))) == vals[::-1]
    if vals:
        left = random.randint(1, len(vals))
        right = random.randint(left, len(vals))
        want = vals[:left - 1] + vals[left - 1:right][::-1] + vals[right:]
        ok &= to_list(reverse_between(from_list(vals), left, right)) == want
print(ok)                                # True

The complexity

The iterative reversal visits each node once and keeps three pointers: O(n) time, O(1) extra space. The recursive version is also O(n) time but uses O(n) stack space, one frame per node, which is why it hits the recursion limit on long inputs. reverse_between is O(right) time: it walks to the section and reverses only the section.

Where it goes wrong

• Flipping before saving. Writing node.next = prev before nxt = node.next makes the rest of the list unreachable. The loop then ends after one node and returns a one-element list.
• Returning head instead of prev. After the loop, head is the old first node, now the tail. The function returns a list of length one.
• Forgetting head.next = None in the recursive version. The old head and the old second node then point at each other, and anything that walks the result loops forever.
• Recursing on production-sized lists. The recursive solution is fine in an interview if you name its O(n) stack cost; in Python it fails at about a thousand nodes by default.

How to say it in an interview

"I don't move nodes, I flip arrows. I keep prev, starting at None, and node, starting at head. At each step I save node.next first, because flipping would lose it, then point node.next at prev and move both pointers forward. When node is None, prev is the old tail and the new head. That's O(n) time and O(1) space. The recursive version reverses the tail and sets head.next.next to head, but it costs O(n) stack, so for long lists I'd use the loop."

The same pointer discipline shows up when you need fast and slow pointers to find the middle before reversing half a list, and when you merge two sorted lists.