Reordering / rotation (Linked List — Reversal Sub-pattern)
Split the list, reverse part of it, and re-weave or rotate the pieces. Draw the before and after pictures first; the rest follows from them.
- ›
"reorder the list as
L0 → Ln → L1 → Ln-1" - ›
"rotate the list to the right by
k" - ›
"group all odd-indexed nodes, then all even-indexed nodes"
- ›
"flatten a list where some nodes have a child list"
Rotate List finds the length, closes the list into a circle, then cuts it in the right place. Odd Even Linked List splits by position into two chains and joins them, with no reversal. Reorder List uses fast & slow, a reversal and a weave. Rotate a Doubly Linked List does the cut from the rotate case, but both next and prev must be fixed at the cut and at the join. Flatten a Multilevel Doubly Linked List splices each child list between a node and its next, and needs the next saved before the splice.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Rotate ListWalkthroughMediumBasic Reinforcement·LeetCode #61
- 2Odd Even Linked ListWalkthroughMediumSlight Variation·LeetCode #328
- 3Reorder ListWalkthroughMediumMedium·LeetCode #143
- 4Rotate Doubly Linked List by N NodesWalkthroughMediumPattern Transfer·GeeksforGeeks
- 5Flatten a Multilevel Doubly Linked ListWalkthroughMediumTricky / Edge Case·LeetCode #430
Template
// Split, reverse, and re-weave: L0 → Ln → L1 → Ln-1 → L2 → …
// Three steps. Find the end of the first half, reverse the second half,
// then interleave the two halves one node at a time.
void reorderList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return;
// 1. Find the end of the first half (fast and slow). slow stops on the first middle.
ListNode* slow = head;
ListNode* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
// 2. Cut the list in two, then reverse the second half.
ListNode* second = slow->next;
slow->next = nullptr; // cut: without this the first half still runs into the second
ListNode* prev = nullptr;
while (second != nullptr) {
ListNode* nxt = second->next;
second->next = prev;
prev = second;
second = nxt;
}
second = prev; // head of the reversed second half (the old tail)
// 3. Weave: take one node from the first half, then one from the second, until one runs out.
ListNode* first = head;
while (second != nullptr) {
ListNode* f = first->next; // save both continuations before relinking
ListNode* s = second->next;
first->next = second; // L0 → Ln
second->next = f; // Ln → L1
first = f;
second = s;
}
}