Pattern Guide
Linked List Reversal Patterns
"Reverse full list, reverse k-groups, reverse between positions, copy with random."
Linked list reversal is a fundamental building block: reverse full list, reverse k-group, reverse between positions, and reorder list. Core technique: three-pointer reversal (prev, curr, next). For k-group: reverse k nodes at a time, reconnect groups. For random pointer copy: two passes or HashMap approach. These patterns test pointer manipulation under pressure.
Problems you can solve with this pattern
4 problems · click any to start solving
// Reverse full linked list
function reverseList(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev; // new head
}
// Reverse nodes in k-group
function reverseKGroup(head, k) {
// Check if k nodes remain
let node = head, count = 0;
while (node && count < k) { node = node.next; count++; }
if (count < k) return head; // less than k nodes left
// Reverse k nodes
let prev = null, curr = head;
for (let i = 0; i < k; i++) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// head is now the tail of this group; connect to next group
head.next = reverseKGroup(curr, k);
return prev; // new head of this group
}Reverse full list: prev=null, curr=head. While curr: save next, reverse pointer, advance. Reverse between m and n: walk to position m, reverse n-m+1 nodes, reconnect. Reverse k-groups: reverse k nodes, recurse on rest, connect. Copy with random pointer: first pass clone without random, second pass set randoms using a HashMap of original→clone.
// Reverse full linked list
function reverseList(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev; // new head
}
// Reverse nodes in k-group
function reverseKGroup(head, k) {
// Check if k nodes remain
let node = head, count = 0;
while (node && count < k) { node = node.next; count++; }
if (count < k) return head; // less than k nodes left
// Reverse k nodes
let prev = null, curr = head;
for (let i = 0; i < k; i++) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// head is now the tail of this group; connect to next group
head.next = reverseKGroup(curr, k);
return prev; // new head of this group
}k-group trick: After reversing k nodes, original head becomes new tail. head.next connects to recursively reversed rest.
Copy with O(1) space (no HashMap): Interleave clones: A→A'→B→B'→C→C'. Set randoms: A'.random = A.random.next. Separate lists: A→B→C and A'→B'→C'.