Pattern visualizer
Flatten a Multilevel Doubly Linked List
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. 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]..
Iterative splice in place — no stack, no recursion
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.
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