Reverse Linked List — All Approaches from Basic to Advanced

Introduction

Reversing a linked list is one of the three most-asked linked list interview questions (alongside cycle detection and finding the middle). It appears directly and as a sub-problem in more complex problems like palindrome check, reverse in groups, and reordering lists.

The key insight that beginners miss: you cannot simply traverse backward like an array. With no random access and (in a singly linked list) no previous pointer, you must manipulate the next pointers directly. Every node's pointer must be reversed individually.

This lesson covers all approaches completely.

Iteration 1 --- next_node = node(2) [save 2 before we lose it] node(1).next = None [1 now points backward to prev] prev = node(1) current = node(2) State: None ← 1 2 → 3 → 4 → 5 → None

--- Iteration 2 --- next_node = node(3) node(2).next = node(1) [2 now points to 1] prev = node(2) current = node(3) State: None ← 1 ← 2 3 → 4 → 5 → None

--- Iteration 3 --- next_node = node(4) node(3).next = node(2) prev = node(3) current = node(4)

--- Iteration 4 --- next_node = node(5) node(4).next = node(3) prev = node(4) current = node(5)

--- Iteration 5 --- next_node = None node(5).next = node(4) prev = node(5) current = None

Loop ends: current is None, return prev = node(5)

Result: 5 → 4 → 3 → 2 → 1 → None ✓

def reverse_list_recursive(head): """ Reverse recursively. Time: O(n), Space: O(n) — call stack depth = n """ # Base case: empty list or single node if head is None or head.next is None: return head # This node is the new head

# Recursively reverse the rest new_head = reverse_list_recursive(head.next)

# At this point, everything after head is already reversed # head.next is the last node of the reversed suffix # Make it point back to head head.next.next = head head.next = None # head is now the new tail

return new_head # Propagate the new head up the call stack

reverse(1 → 2 → 3 → None)

Call 1: head=1 Calls reverse(2 → 3 → None)

Call 2: head=2 Calls reverse(3 → None)

Call 3: head=3, head.next=None → BASE CASE, return 3

Back in Call 2: new_head=3, head=2 head.next.next = head → 3.next = 2 head.next = None → 2.next = None return 3

State: 3 → 2 → None (head still points to 1 via external ref)

Back in Call 1: new_head=3, head=1 head.next.next = head → 2.next = 1 (head.next is 2, which points to 1) head.next = None → 1.next = None return 3

Final: 3 → 2 → 1 → None ✓

def reverse_between(head, m, n): """ Reverse nodes from position m to n (1-indexed). Example: [1,2,3,4,5], m=2, n=4 → [1,4,3,2,5] Time: O(n), Space: O(1) """ if m == n or not head: return head

dummy = Node(0) dummy.next = head before_m = dummy # Node just before position m

# Move before_m to position m-1 for _ in range(m - 1): before_m = before_m.next

# current = node at position m (start of sublist to reverse) current = before_m.next # next_node = node at position m+1 next_node = current.next

# Reverse by repeatedly moving next_node to just after before_m for _ in range(n - m): current.next = next_node.next # Current skips over next_node next_node.next = before_m.next # next_node points to current head of reversed portion before_m.next = next_node # before_m points to next_node (new head of reversed portion) next_node = current.next # Advance next_node

return dummy.next

Initial: dummy → 1 → 2 → 3 → 4 → 5 → None before_m = node(1) current = node(2), next_node = node(3)

Iteration 1 (i=1 of n-m=2): current.next = node(4) next_node.next = node(2) → 3 → 2 before_m.next = node(3) Result: 1 → 3 → 2 → 4 → 5 next_node = node(4)

Iteration 2 (i=2 of n-m=2): current.next = node(5) next_node.next = node(3) → 4 → 3 before_m.next = node(4) Result: 1 → 4 → 3 → 2 → 5 ✓

def reverse_k_group(head, k): """ Reverse every k nodes as a group. If remaining < k, leave as-is. [1,2,3,4,5], k=2 → [2,1,4,3,5] [1,2,3,4,5], k=3 → [3,2,1,4,5] Time: O(n), Space: O(n/k) for recursion """ # Count if k nodes remain count = 0 node = head while node and count < k: node = node.next count += 1

if count < k: return head # Not enough nodes, leave as-is

# Reverse k nodes prev = None current = head for _ in range(k): next_node = current.next current.next = prev prev = current current = next_node

# head is now the tail of the reversed group # Recursively process the rest and attach head.next = reverse_k_group(current, k)

return prev # prev is the new head of this group

Iterative version (O(1) space):

def reverse_k_group_iterative(head, k): """Iterative k-group reversal. O(n) time, O(1) space.""" dummy = Node(0) dummy.next = head group_prev = dummy

while True: # Find the end of the current group kth = get_kth_node(group_prev, k) if not kth: break

group_next = kth.next

# Reverse the group prev = group_next current = group_prev.next while current != group_next: next_node = current.next current.next = prev prev = current current = next_node

# Connect the group temp = group_prev.next # Save old start (new end of group) group_prev.next = kth # Connect to new start (kth) group_prev = temp # Advance group_prev to end of reversed group

return dummy.next

def get_kth_node(current, k): """Return the kth node from current, or None if fewer than k nodes remain.""" while current and k > 0: current = current.next k -= 1 return current

def reverse_alternate_k_groups(head, k): """ Reverse alternate k groups. [1,2,3,4,5,6,7,8], k=2 → [2,1,3,4,6,5,7,8] (reverse 2, keep 2, reverse 2, keep 2) """ current = head prev = None count = 0

# Reverse k nodes while current and count < k: next_node = current.next current.next = prev prev = current current = next_node count += 1

# Connect original head (now tail) to the result of recursion if head: head.next = current # Skip k nodes (original head is now the tail)

# Skip k nodes count = 0 while current and count < k - 1: current = current.next count += 1

# Recursively process the rest if current: current.next = reverse_alternate_k_groups(current.next, k)

return prev # New head

WRONG — loses the rest of the list:

current.next = prev prev = current current = current.next # ERROR: current.next was just set to prev!

CORRECT:

next_node = current.next # Save FIRST current.next = prev prev = current current = next_node

WRONG — current is None when loop ends

return current

CORRECT — prev is the new head (last processed node)

return prev

def reverse_list(head): if not head or not head.next: # Always check these! return head # ...