These are composite patterns — each decomposes into operations you already know:
Reorder = middle → reverse → merge Flatten = splice child list in place Random copy = interweave → set randoms → separate
Pattern 1: Reorder List (L0→Ln→L1→Ln−1)
[1,2,3,4,5] becomes 1→5→2→4→3 via split, reverse and interleave. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Reorder List
Reorder a list L0→L1→…→Ln into L0→Ln→L1→Ln−1→… in place.
Three phases on the same nodes: slow/fast to find the middle, cut and reverse the second half, then interleave the first half with the reversed second.
1
# 1. find middle (slow/fast)
2
while fast.next && fast.next.next: slow++, fast += 2
3
# 2. cut + reverse second half
4
second = slow.next; slow.next = null; reverse(second)
5
# 3. interleave first & reversed-second
6
first.next = second; swap advance both
public void reorderList(ListNode head) {
if (head == null) return;
// 1. find middle (slow ends at end of first half)
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. reverse second half
ListNode second = slow.next;
slow.next = null; // split!
ListNode prev = null;
while (second != null) {
ListNode next = second.next;
second.next = prev;
prev = second;
second = next;
}
// 3. merge alternating
ListNode first = head;
while (prev != null) {
ListNode t1 = first.next, t2 = prev.next;
first.next = prev;
prev.next = t1;
first = t1;
prev = t2;
}
}def reorder_list(head):
if not head:
return
# 1. find middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 2. reverse second half
second, slow.next = slow.next, None # split!
prev = None
while second:
second.next, prev, second = prev, second, second.next
# 3. merge alternating
first = head
while prev:
first.next, prev.next = prev, first.next
first = first.next.next
prev = prev.nextvoid reorderList(ListNode* head) {
if (!head) return;
// 1. find middle
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
// 2. reverse second half
ListNode* second = slow->next;
slow->next = nullptr; // split!
ListNode* prev = nullptr;
while (second) {
ListNode* next = second->next;
second->next = prev;
prev = second;
second = next;
}
// 3. merge alternating
ListNode* first = head;
while (prev) {
ListNode *t1 = first->next, *t2 = prev->next;
first->next = prev;
prev->next = t1;
first = t1;
prev = t2;
}
}function reorderList(head) {
if (!head) return;
// 1. find middle
let slow = head,
fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// 2. reverse second half
let second = slow.next;
slow.next = null; // split!
let prev = null;
while (second) {
const next = second.next;
second.next = prev;
prev = second;
second = next;
}
// 3. merge alternating
let first = head;
while (prev) {
const t1 = first.next,
t2 = prev.next;
first.next = prev;
prev.next = t1;
first = t1;
prev = t2;
}
}Split the list BEFORE reversing — otherwise the reversed tail loops back into the front half.
Pattern 2: Flatten Multilevel List
Child chains get spliced into the main line right after their parent. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Flatten Multilevel Linked List
Flatten a multilevel list so every child chain is spliced in right after its parent, in DFS order.
Walk the list; whenever a node has a child, splice the whole child chain in immediately after it (wire child before the next node and the chain's tail back to that next node), then keep walking.
1
cur = head
2
while cur:
3
if cur.child:
4
splice child chain after cur
5
cur = cur.next
Each node may have a child list — splice it in using a stack:
public Node flatten(Node head) {
Deque<Node> stack = new ArrayDeque<>();
Node cur = head;
while (cur != null) {
if (cur.child != null) {
if (cur.next != null)
stack.push(cur.next); // resume later
cur.next = cur.child; // splice child in
cur.next.prev = cur;
cur.child = null;
} else if (cur.next == null && !stack.isEmpty()) {
cur.next = stack.pop(); // attach saved branch
cur.next.prev = cur;
}
cur = cur.next;
}
return head;
}def flatten(head):
stack = []
cur = head
while cur:
if cur.child:
if cur.next:
stack.append(cur.next) # resume later
cur.next, cur.child.prev = cur.child, cur
cur.child = None
elif not cur.next and stack:
cur.next = stack.pop() # attach saved branch
cur.next.prev = cur
cur = cur.next
return headNode* flatten(Node* head) {
stack<Node*> st;
Node* cur = head;
while (cur) {
if (cur->child) {
if (cur->next)
st.push(cur->next); // resume later
cur->next = cur->child; // splice child in
cur->next->prev = cur;
cur->child = nullptr;
} else if (!cur->next && !st.empty()) {
cur->next = st.top(); // attach saved branch
st.pop();
cur->next->prev = cur;
}
cur = cur->next;
}
return head;
}function flatten(head) {
const stack = [];
let cur = head;
while (cur) {
if (cur.child) {
if (cur.next) stack.push(cur.next); // resume later
cur.next = cur.child; // splice child in
cur.next.prev = cur;
cur.child = null;
} else if (!cur.next && stack.length) {
cur.next = stack.pop(); // attach saved branch
cur.next.prev = cur;
}
cur = cur.next;
}
return head;
}DFS order via explicit stack — the branch you pause becomes the branch you resume.
Pattern 3: Copy List With Random Pointer
Weave clones behind originals; random links copy themselves. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Copy List With Random Pointer
Deep-copy a linked list whose nodes also carry random pointers.
Weave each clone directly after its original, set clone.random via the one-hop rule (orig.random.next), then unweave into the original and the copy. Avoids an extra hash map.
1
weave: clone each node after its original
2
clone.random = orig.random.next // twin sits one hop past target
3
unweave into original + copy
Interweave clones, wire randoms, then separate:
public Node copyRandomList(Node head) {
if (head == null) return null;
// 1. interweave: A → A' → B → B'
for (Node cur = head; cur != null; cur = cur.next.next) {
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
// 2. set randoms on copies
for (Node cur = head; cur != null; cur = cur.next.next)
if (cur.random != null)
cur.next.random = cur.random.next;
// 3. separate the two lists
Node dummy = new Node(0), tail = dummy;
for (Node cur = head; cur != null; cur = cur.next) {
tail.next = cur.next;
tail = tail.next;
cur.next = tail.next;
}
return dummy.next;
}def copy_random_list(head):
if not head:
return None
# 1. interweave: A → A' → B → B'
cur = head
while cur:
copy = Node(cur.val)
copy.next = cur.next
cur.next = copy
cur = cur.next.next
# 2. set randoms on copies
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 3. separate the two lists
dummy = tail = Node(0)
cur = head
while cur:
tail.next = cur.next
tail = tail.next
cur.next = tail.next
cur = cur.next
return dummy.nextNode* copyRandomList(Node* head) {
if (!head) return nullptr;
// 1. interweave: A → A' → B → B'
for (Node* cur = head; cur; cur = cur->next->next) {
Node* copy = new Node(cur->val);
copy->next = cur->next;
cur->next = copy;
}
// 2. set randoms on copies
for (Node* cur = head; cur; cur = cur->next->next)
if (cur->random)
cur->next->random = cur->random->next;
// 3. separate the two lists
Node dummy(0), *tail = &dummy;
for (Node* cur = head; cur; cur = cur->next) {
tail->next = cur->next;
tail = tail->next;
cur->next = tail->next;
}
return dummy.next;
}function copyRandomList(head) {
if (!head) return null;
// 1. interweave: A → A' → B → B'
for (let cur = head; cur; cur = cur.next.next) {
const copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
// 2. set randoms on copies
for (let cur = head; cur; cur = cur.next.next)
if (cur.random) cur.next.random = cur.random.next;
// 3. separate the two lists
const dummy = new Node(0);
let tail = dummy;
for (let cur = head; cur; cur = cur.next) {
tail.next = cur.next;
tail = tail.next;
cur.next = tail.next;
}
return dummy.next;
}The clone sitting directly after its original makes
random.nextthe copy’s random — no HashMap needed.
Common Mistakes
Reversing before splitting.
The second half’s arrows point back through the first half — always cut at the middle first.
Forgetting prev pointers when flattening doubly-linked children.
Child splicing must fix both next AND prev.
Separating interleaved clones too early.
Randoms must be assigned while originals and clones are still adjacent.
Complexity
| Operation | Time | Space |
|---|---|---|
| Reorder | O(n) | O(1) |
| Flatten | O(n) | O(depth) stack |
| Random copy | O(n) | O(1) extra |
Premium Content
Unlock Flatten & Reorder and all premium lessons with a subscription.
From ₹199.99/year — See plans