After flattening the multilevel linked list it becomes:
Problem overview
The method flatten receives the head of a doubly linked list. Besides prev and next, each node has a child link, which may point to the head of another doubly linked list, and that list's nodes may have children too. The method must turn the structure into one level, in place, and return the head.
In the example, the top level is 1, 2, 3, 4, 5, 6. Node 3 has the child list 7, 8, 9, 10, and node 8 has the child list 11, 12. Each child list goes right after its parent and before the parent's old successor, so the result is 1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6. Afterwards no node has a child, and the prev links agree with the next links.
Approach: splice as the walk reaches each parent
The other lesson on this problem flattens each child list recursively. This one needs no recursion. It uses one walker that moves through the list with next. When the walker lands on a node with a child, it splices the child list in without flattening it first.
The splice has the same shape every time. Save the node's successor, find the last node of the child list, join the node to the child, and join the child's last node to the saved successor. A helper getTail finds that last node by following next from the child until there is none.
The child list may still contain nodes with children of their own, and that's fine. After the splice, the walker moves to node.next, which is now the first child node. It then walks through the spliced nodes, and when it reaches one that has a child, it splices that one in the same way. Deeper levels get flattened when the walk arrives at their parents.
This also explains why getTail only needs to follow next on the child's own level. Any node on that level with a child will get its child spliced later, after the walker has moved on.
Step by step
- Start a walker.
var node = head. The parameterheadstays unchanged because it is what the method returns. - Loop while
node != nil. - Check for a child with
node!.child != nil. The!is safe because the loop condition just checked the node. - Save the successor in
let next = node!.next, before the link is overwritten. - Find the child list's last node with
getTail(node!.child)and keep it inchildTail. - Link the node and the child both ways:
node!.next = node!.childandnode!.child!.prev = node. - Clear
node!.child. It still has to be read by the two lines before, so it can only be cleared after them. - Link the child's tail to the saved successor:
childTail!.next = next, and whennextexists,next!.prev = childTail. - Advance with
node = node!.next, outside theif. After a splice this enters the child list, so the walk reaches deeper levels. - Return
head. Returningnodewould be wrong, because it isnilafter the loop. - Write
getTail. It copies its parameter into a mutablevar nodeand advances whilenode!.next != nil. It stops on the last node, not on thenilafter it.
The solution in Swift
class Solution {
func getTail(_ node: Node?) -> Node? {
var node = node
while node!.next != nil {
node = node!.next
}
return node
}
func flatten(_ head: Node?) -> Node? {
var node = head
while node != nil {
if node!.child != nil {
let next = node!.next
let childTail = getTail(node!.child)
node!.next = node!.child
node!.child!.prev = node
node!.child = nil
childTail!.next = next
if next != nil {
next!.prev = childTail
}
}
node = node!.next
}
return head
}
}
Swift details to notice:
- Parameters are constants.
var node = nodeingetTailmakes a new mutable variable that shadows the parameter, so the loop can move it. - A crash on
nil.getTailunwraps its argument with!. Calling it withnilstops the program at run time. It is only called on a child that was checked to exist. - Classes are shared.
Nodeis a class, sonode!.next = ...changes the real node. That is why the list is flattened in place and returningheadis enough. - Optional comparison.
next != nilworks for any optional type. It doesn't requireNodeto beEquatable.
Complexity
Time: O(n). Each node is walked by the main loop once. It is also walked once by getTail, as part of the level it belongs to, and only before its parent is spliced. Each node therefore costs a constant number of steps in total.
Space: O(1). There is no recursion and nothing is allocated, only a few references. This is the advantage over the recursive version, which uses one stack frame per level of nesting, and which can revisit nodes once per level above them.
Edge cases and common mistakes
- Empty list.
flatten(nil)returnsnil, because the loop never runs. - No children. The list comes back unchanged.
- Child on the last node of a level.
nextisnil, so the child's tail ends the list, and no back link is set.1, 2with a child3, 4on node 2 becomes1, 2, 3, 4. - Child on the head.
1, 2with a child3on node 1 becomes1, 3, 2. - Children inside children. The example needs this: node 8 sits inside the list that was spliced in for node 3, and its child is spliced when the walker gets to 8.
- Stopping
getTailtoo late. The loop condition must testnode!.next. Testingnodeitself would run past the last node and returnnil. - Not clearing
child. The result would still carry child links, so it would not be a single-level list.
Testing
- The example above gives
1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6, with no children left and matchingprevlinks. - An empty list gives an empty list.
1, 2, 3with no children stays1, 2, 3.1, 2with a child3, 4on node 2 gives1, 2, 3, 4.1, 2with a child3on node 1 gives1, 3, 2.
