After flattening the multilevel linked list it becomes:
Problem overview
Each node of the list has prev and next pointers, like a normal doubly linked list, plus a child pointer. A child, when it isn't null, is the head of another doubly linked list, and nodes of that list can have children too. The method flatten receives the head of the top level and must turn the whole structure into one single-level doubly linked list. It returns the head, and the lesson asks for a recursive solution that runs in O(n) time.
The rule is that a child list goes right after its parent and before the parent's old next. In the first example, the node 3 has a child list 7, 8, 9, 10, and node 8 has a child list 11, 12. The flattened order is 1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6. In the second example, [1, 2] where 1 has the child 3 becomes 1, 3, 2.
After flattening, no node may keep a child pointer, and every prev pointer must match the new order.
Approach: flatten the child first, then splice it in
Walk along a level. When a node has a child, three things have to happen: the child list gets flattened (it may contain children of its own), the flattened child list is inserted between the node and its old next, and the node's child is cleared.
The recursion handles the first part. Call the same function on the child. It flattens that sub-list in place and tells you where the flattened sub-list ends. That last node is the tail, and it is what you need to reconnect the rest of the current level.
So the helper flattenLevel does two jobs: it flattens in place, and it returns the last node of the flattened list. The public method flatten only needs the first job, because the head never changes.
Take [1, 2] where node 1 has the child 3. At node 1, save next (node 2). Flatten the child, whose tail is node 3. Link 1 and 3 in both directions, clear the child, then link node 3 to node 2 in both directions. The list is now 1, 3, 2.
Step by step
- Delegate to a helper.
flattencallsthis.flattenLevel(head)and returnshead. Splicing only rewires pointers, so the first node stays first. - Declare
flattenLevel. It takes and returnsNode | null. The parameter can benullfor an empty list, and the walking variable ends asnull. - Track the last visited node in
tail, starting withnode. For an empty list the loop never runs and the function returnsnull. - Loop while
nodeis truthy to visit every node on the level. - Check for a child. Only nodes with a child need rewiring.
- Save
node.nextinnext. The next assignment overwritesnode.next, and without this copy the rest of the level would be lost. - Recurse on
node.childand keep the result inchildTail. The recursive call also flattens deeper levels. - Link the node and its child in both directions:
node.next = node.childandnode.child.prev = node. Both lines readnode.child, so they come before it is cleared. - Clear
node.childby setting it tonull. - Link
childTailtonext. SetchildTail.next = next, and ifnextexists, setnext.prev = childTail. When the parent was the last node of its level,nextisnulland there is no node to point back. - Advance. Set
tail = node, thennode = node.next. After a splice,node.nextis the first child node, so the loop walks through the spliced nodes too, andtailends on the real last node. - Return
tailafter the loop. This is the value the recursive call stores inchildTail.
The solution in TypeScript
class Solution {
flattenLevel(node: Node | null): Node | null {
let tail = node;
while (node) {
if (node.child) {
let next = node.next;
let childTail = this.flattenLevel(node.child);
node.next = node.child;
node.child.prev = node;
node.child = null;
childTail!.next = next;
if (next) {
next.prev = childTail;
}
}
tail = node;
node = node.next;
}
return tail;
}
flatten(head: Node | null): Node | null {
this.flattenLevel(head);
return head;
}
}
The TypeScript details worth knowing:
- Mutating a parameter. The loop reassigns
node. That changes only the local variable. The caller'sheadstill refers to the first node, which is whyflattencan return it. - Order of the assignments.
node.child.prev = nodereadsnode.child, so it has to run beforenode.child = null. After that line,node.childisnulland there is no node to give aprev. - The assertion
childTail!.flattenLevelis typed to possibly returnnull, but for a non-null child it returns a real node. The!tells the compiler to accept that. The compiled JavaScript has no trace of it, so no check happens at run time. - The name
Node. The lesson supplies its ownNodeclass withval,prev,nextandchild. Use that one.
Complexity
Time: O(n). The main loop walks each level node by node. After a splice it continues into the child nodes, which were already flattened, and they have no children left, so each one is visited by the loop only a constant number of times. Rewiring a node costs a fixed number of assignments.
Space: O(d), where d is the deepest nesting of child lists. The only extra memory is the recursion stack, one frame per level. In the worst case, where every node is the only child of the previous one, d is n, but typical inputs are much shallower.
Edge cases and common mistakes
- An empty list.
flatten(null)returnsnull, because the loop never runs. - No children. The list comes back unchanged.
- A child on the last node of a level. 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 code would fail by readingprevofnull. - Forgetting to clear
child. The values look right, but nodes still point at their old child lists, so the structure is not flat. - Forgetting
prevpointers. A list that is correct going forward but not backward is not a valid doubly linked list. For the first example, walking back from node 6 should give6, 5, 4, 10, 9, 12, 11, 8, 7, 3, 2, 1. - Losing the rest of the level. Overwriting
node.nextbefore saving it intonextmakes nodes 4, 5 and 6 unreachable. - Returning the wrong thing.
flattenreturns the original head. Returning what the helper returns would give the last node.
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.