After flattening the multilevel linked list it becomes:
Problem overview
Each node has prev and next pointers plus a child pointer. A child, when it isn't null, is the head of another doubly linked list, and nodes of that list may have children of their own. The method flatten receives the head of the top level and must make one single-level doubly linked list, in place. This version of the lesson asks for an iterative solution, with no recursion, in O(n) time.
A child list goes right after its parent and before the parent's old next. In the first example, node 3 has the child list 7, 8, 9, 10, and node 8 has the child list 11, 12. The flattened order is 1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6. For [1, 2] where node 1 has the child 3, the result is 1, 3, 2. No node may keep a child pointer, and every prev must match the new order.
Approach: splice as you walk
A single loop walks the list from the head. When the current node has a child, splice the child list in right after it: the parent's next becomes the child, and the last node of the child list is linked to the parent's old next. Then simply keep walking. The next node in the walk is the first child node, so the loop passes through the spliced nodes. If one of those has a child, it is spliced when the loop reaches it.
That is why no recursion is needed. A deeper child list doesn't have to be flattened before the splice. It is flattened later, when the walk arrives at its parent, and by that time the parent is already part of the main level.
To reconnect the end of the child list, you need its last node. A helper, getTail, walks forward from the child's head until there is no next. It only walks the child's own level, which hasn't been spliced into yet, so each node is scanned by it at most once.
Trace [1, 2] where node 1 has the child 3. At node 1, next is saved as node 2. The tail of the child list is node 3. Link 1 to 3 both ways, clear the child, link 3 to 2 both ways. The loop moves to node 3, then to node 2, then to null.
Step by step
- Walk with a separate variable. Start
nodeathead, soheadstays available to return. - Loop while
nodeis truthy. An object is truthy andnullis falsy, so an empty list never enters the loop. - Check for a child. Only nodes with a child need rewiring.
- Save
node.nextinnext. The next line overwrites it, so without the copy the rest of the level would be lost. - Find the child list's last node with
this.getTail(node.child)and keep it inchildTail. The helper looks only at the child's own level. - Link the node and its child both ways:
node.next = node.childandnode.child.prev = node. Both readnode.child, so they run before it is cleared. - Clear
node.childby setting it tonull. - Link
childTailtonext: setchildTail.next = next, and ifnextexists, setnext.prev = childTail. If the parent ended its level,nextisnulland there is nothing to point back. - Advance with
node = node.next. After a splice this moves into the child nodes, so nested levels get flattened one by one. - Return
head. The first node never changes. Returningnodewould givenull, because the loop ends when it becomesnull. - Write
getTail: while the current node has anext, move to it, then return the node. Stop on the node whosenextisnull, not onnullitself, because you want the last node.
The solution in TypeScript
class Solution {
getTail(node: Node | null): Node | null {
while (node!.next) {
node = node!.next;
}
return node;
}
flatten(head: Node | null): Node | null {
let node = head;
while (node) {
if (node.child) {
let next = node.next;
let childTail = this.getTail(node.child);
node.next = node.child;
node.child.prev = node;
node.child = null;
childTail!.next = next;
if (next) {
next.prev = childTail;
}
}
node = node.next;
}
return head;
}
}
The TypeScript details worth knowing:
- The assertion
!.getTailtakesNode | null, andnode!.nexttells the compiler to treatnodeas non-null. It is only a promise. The compiled JavaScript has no trace of it, so passingnullwould throw aTypeErrorat run time. The call site only passes a child that exists. - Same shape as
head.let node = head;givesnodethe typeNode | null, inferred fromhead. Reassigning it never changeshead. - Order of the assignments.
node.child.prev = nodemust run beforenode.child = null. After the second line there is no child to update. - Methods.
this.getTail(...)needs thethis.prefix, as for any method of the class. The lesson supplies its ownNodeclass withval,prev,nextandchild.
Complexity
Time: O(n). The main loop visits every node once. getTail walks a child level before it is spliced, and the loop later walks the same nodes as part of the main level. Each node is scanned by getTail at most once, because after a level is spliced, no later getTail call starts inside it. So the total work is a small multiple of n.
Space: O(1). There is no recursion and no extra container, only a few local variables. That is the advantage of this version over the recursive one, whose stack grows with the nesting depth.
Edge cases and common mistakes
- An empty list.
flatten(null)returnsnull, because the loop never runs. - No children. The loop walks to the end and returns the same list.
- A child on the last node. For
[1, 2]with a child list[3, 4]on node 2,nextisnull. The result is1, 2, 3, 4, and without theif (next)check, the linenext.prev = childTailwould throw aTypeError. - Calling
getTailon the parent. It would return the end of the parent's level, not the child's, and the splice would link the wrong nodes. - Forgetting to clear
child. The order of values looks right, but each spliced node still points to its old list, so the structure is not flat. - Forgetting
prev. For the first example, walking backwards from node 6 should give6, 5, 4, 10, 9, 12, 11, 8, 7, 3, 2, 1. - Skipping the spliced nodes. The advance must read
node.nextafter the splice. If the loop jumped to the savednext, nested children would stay unflattened.
Testing
- The three-level list from the first example gives
1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6. [1, 2]with a child[3]on node 1 gives1, 3, 2.[1, 2]with a child[3, 4]on node 2 gives1, 2, 3, 4.- An empty list gives an empty list.