In-place List Reversal
Carry three pointers, previous, current and next, and flip one link per iteration.
Linked ListO(n) time, O(1) spaceNew7 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
reverse a list or a sublist
reverse in groups of k
palindrome linked list
The template
Get this into muscle memory, then adapt the condition per problem.
let prev = null, cur = head;
while (cur) {
const nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev; Watch Reverse a Linked ListIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Save the next pointer before you overwrite it.
- 2Draw three nodes and trace one iteration by hand.
- 3For sublists, keep pointers to the node before and after the section.
Drill it
Every problem in the bank that uses this pattern.
0 / 7 solved