Flatten a Multilevel Doubly Linked List
Iterative splice in place — no stack, no recursion
A child branch is a detour: everything after its owner on the current level must wait until the whole branch, including any branches nested inside it, has been visited. Recursion or an explicit stack remembers the suspended next pointer, but a doubly linked list can remember it for free by rewiring. When cur has a child, walk to the branch's tail, connect that tail to cur.next, connect cur.next to the branch head, and clear the child pointer. The branch is now part of the ordinary next chain, so the same forward walk continues straight into it and meets any deeper child on the way. The two details that break submissions are the prev pointers — the branch head's prev must become cur and the suspended node's prev must become the tail — and the guard for a NULL cur.next when the owner is the last node of its level.
Details
Animated on: Level 1 is [1, 2, 3, 4, 5, 6]; node 3 owns the child branch [7, 8, 9, 10] and node 8 inside it owns [11, 12]. Flatten into one doubly linked level. Answer: [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6].
Problem:Flatten a Multilevel Doubly Linked ListMedium
Iterative splice in place — no stack, no recursion
step 1 / 12
Only the next chain is drawn: [1, 2, 3, 4, 5, 6]. Hidden below it, 3 owns [7, 8, 9, 10]; 8 owns [11, 12]. The goal is one level where every branch sits right after its owner, so cur walks forward and splices each branch in the moment it is met.
- cur=0· arr[0] = 1
1FUNCTION flatten(head)2 cur <- head3 WHILE cur != NULL4 IF cur.child != NULL5 tail <- TAIL(cur.child)6 tail.next <- cur.next7 IF cur.next != NULL8 cur.next.prev <- tail9 cur.next <- cur.child10 cur.child.prev <- cur11 cur.child <- NULL12 cur <- cur.next13 RETURN head
← / → step · space play · Home restart
Every step in words
Show all 12 steps
- Only the next chain is drawn: [1, 2, 3, 4, 5, 6]. Hidden below it, 3 owns [7, 8, 9, 10]; 8 owns [11, 12]. The goal is one level where every branch sits right after its owner, so cur walks forward and splices each branch in the moment it is met.
- 1, 2 had no child, so cur just moved on. cur=3 has child branch [7, 8, 9, 10]. Everything after 3 on this level must wait until the whole branch has been visited, exactly like a recursive call must finish before the caller resumes.
- Walk the branch to its end: tail=10. The branch has to be reattached at BOTH ends, and the far end is only known after this walk. Each node is walked as a tail at most once, so the total stays O(n).
- Four rewirings, in this order: tail.next <- 4, then 4.prev <- 10; cur.next <- 7, then 7.prev <- 3; finally cur.child <- NULL. The branch now lives between 3 and 4, with prev pointers intact in both directions.
- cur <- cur.next lands on 7, the first node of the branch just spliced in. Because the branch was folded into the next chain, no stack or recursion is needed to visit it: the same loop simply keeps walking, and any child found deeper inside is handled the same way.
- 7 had no child, so cur just moved on. cur=8 has child branch [11, 12]. Everything after 8 on this level must wait until the whole branch has been visited, exactly like a recursive call must finish before the caller resumes.
- Walk the branch to its end: tail=12. The branch has to be reattached at BOTH ends, and the far end is only known after this walk. Each node is walked as a tail at most once, so the total stays O(n).
- Four rewirings, in this order: tail.next <- 9, then 9.prev <- 12; cur.next <- 11, then 11.prev <- 8; finally cur.child <- NULL. The branch now lives between 8 and 9, with prev pointers intact in both directions.
- cur <- cur.next lands on 11, the first node of the branch just spliced in. Because the branch was folded into the next chain, no stack or recursion is needed to visit it: the same loop simply keeps walking, and any child found deeper inside is handled the same way.
- cur steps from 12 to 9 — that is the seam where a spliced branch tail rejoins the next pointer it had suspended. Nothing special happens here: the earlier rewiring made the branch part of the ordinary next chain, so the plain walk carries on through it.
- cur steps from 10 to 4 — that is the seam where a spliced branch tail rejoins the next pointer it had suspended. Nothing special happens here: the earlier rewiring made the branch part of the ordinary next chain, so the plain walk carries on through it.
- cur is NULL, so the walk is over. Reading next pointers from head gives [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6] — the pre-order of the original structure (owner, then its whole branch, then the rest of its level). Every child pointer is NULL and every node's prev points at the node before it, which is what makes the result a valid single-level doubly linked list.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.