Reversing a Linked List
Reverse a singly linked list iteratively with three-pointer rewiring and recursively, tracing each step on a whiteboard-style diagram.
Why List Reversal Is Essential
Reversing a linked list is among the most frequently asked coding interview questions. It tests your ability to manipulate pointers precisely without losing track of nodes. Variants appear as standalone problems and as sub-steps inside larger algorithms like palindrome detection, reorder list, and k-group reversal.
The iterative approach uses three pointers: prev, curr, and next_node. The recursive approach expresses the same logic as a call-stack traversal. Both achieve O(n) time and, for iterative, O(1) space.
Three-Pointer Iterative Reversal
At each step of the iterative reversal: save curr.next so you do not lose the rest of the list, flip curr.next to point backward to prev, advance prev to curr, and advance curr to the saved next. When curr becomes None the loop ends and prev is the new head.
A useful mnemonic: Save, Flip, Advance, Advance.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # Save
curr.next = prev # Flip
prev = curr # Advance prev
curr = next_node # Advance curr
return prev # new head
# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
print(head.val, end=' ') # 5 4 3 2 1
head = head.next