Linked List Reversal
The Intuition
You have a chain of paper clips linked together. You want to reverse the chain. Here's what you do: hold the first clip, unhook it from the second, and set it aside to start a new chain. Now pick up the second clip, unhook it from the third, and attach it before the first clip in your new chain. Keep going. Every clip you detach gets placed at the front of the new chain.
When you're done, the clip you picked up last is at the front, and the clip you picked up first is at the back. Reversed.
In code, you need three pointers to pull this off. current is the clip you're about to detach. prev is the growing reversed chain behind you. And you need to save next before you break the link, because once you point current.next to prev, you've lost your reference to the rest of the original chain. Save it, break it, move on. That's the entire loop: save next, reverse the pointer, advance both prev and current one step forward.
Reversing entire or partial linked lists, checking palindromes, reordering nodes, or any problem requiring reversed traversal of a singly linked list.
- Need random access by index (use array)
- Need to reverse based on values not position (use sorting)
- Circular linked list without clear start/end
Variations:
- Full reversal: Reverse the entire list.
- Partial reversal: Reverse between positions left and right.
- K-group reversal: Reverse every k nodes (combines with length counting).
- empty list
- single node
- two nodes
Key Points
- •Use three pointers: prev, current, next
- •Save next before breaking the link
- •Iterative approach is preferred for O(1) space
- •For partial reversal, track the node before the segment
- •Recursive approach uses O(n) call stack space
Code Template
1 class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6 def reverse_list(head):
7 """Reverse entire linked list iteratively."""
8 prev = None
9 current = head
10 while current:
11 next_node = current.next
12 current.next = prev
13 prev = current
14 current = next_node
15 return prev
16
17 def reverse_between(head, left, right):
18 """Reverse nodes from position left to right (1-indexed)."""
19 dummy = ListNode(0, head)
20 prev = dummy
21 for _ in range(left - 1):
22 prev = prev.next
23
24 current = prev.next
25 for _ in range(right - left):
26 next_node = current.next
27 current.next = next_node.next
28 next_node.next = prev.next
29 prev.next = next_node
30
31 return dummy.nextCommon Mistakes
- Losing reference to the next node before reassigning
- Not returning the new head (previously the tail)
- Off-by-one when reversing a sub-section of the list