← All patternsIn-Place Linked List Reversal · template
Pattern · Linked Lists
In-Place Linked List Reversal
Walk the list with prev, curr and next, turning each arrow around as you go.
Time O(n) · Space O(1)
Taught in Module 8: Linked Lists
Think of it like this
A conga line turning around: each person, one at a time, lets go of the person in front and grabs the person behind.
Clues that point here
- → Reverse a list or part of it
- → Reverse in groups of k
- → Palindrome linked list
- → Reorder list
Not this pattern when
- ✕ You can't modify the list (use a stack or copy)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next; // remember the rest
curr.next = prev; // turn the arrow around
prev = curr; // move both forward
curr = next;
}
return prev; // new headCommon versions
- Reverse linked list
- Reverse between positions m and n
- Reverse nodes in k-group
- Palindrome linked list
- Reorder list
Practice problems with this pattern
8.1Reverse Linked ListEasymain pattern8.7Palindrome Linked ListEasymain pattern8.8Reorder ListMediummain pattern