In-Place Reversal of LinkedList Pattern
Reverse pointers segment by segment without extra space using prev/curr/next bookkeeping.
When to Use It
Reverse a linked list, reverse k-group, reverse a sublist, palindrome linked list.
Classic example: Reverse a singly linked list.
How It Works
Reversing a singly linked list in place is a three-pointer dance: prev, curr, next. At each step you save curr.next, point curr.next at prev, then advance prev and curr forward. The loop ends when curr is null, and prev is the new head. O(n) time, O(1) space: recursion gets the same time but pays O(n) stack.
The pattern scales to sublist reversal and k-group reversal by reversing a bounded segment, then stitching the reversed segment back into the surrounding list. The stitching is where bugs live: you need to remember the node before the segment and the node after, and reconnect both ends carefully. A dummy head node simplifies the case where the segment includes the original head.
For k-group reversal, the trick is to first walk k nodes to confirm the group exists (otherwise leave it alone, per the typical problem statement), then reverse exactly k pointers, then recursively or iteratively process the next group.
Key Insight
Three pointers (prev, curr, next) suffice because reversing one edge only requires knowing the predecessor and successor: there's no need to materialize the reversed list elsewhere, making it O(1) extra space.
Templates
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevCommon Pitfalls
- Forgetting to save next before overwriting curr.next, losing the rest of the list.
- Returning curr (which is null) instead of prev as the new head.
- In sublist reversal, forgetting to null-terminate the reversed segment before stitching, creating cycles.
- Not using a dummy head when the reversal can touch the original head, requiring annoying special cases.
- In k-group reversal, partially reversing a final group that doesn't have k nodes when the problem says to leave it.
Variations
- Full reversal: three-pointer iterative, or recursive returning the new head.
- Reverse sublist between positions m and n: dummy head + reverse-in-place + stitch.
- Reverse in k-groups: walk k, reverse k, recurse/iterate on remainder.
- Palindrome linked list: reverse second half in place, compare with first half, optionally restore.
Big O
- Time
- O(n)
- Space
- O(1)