After flattening the multilevel linked list it becomes:
Problem overview
The method flatten receives the head of a doubly linked list whose nodes have prev and next links and one more link, child. A child points to the head of a separate doubly linked list, and that list's nodes may have children of their own, so the structure has several levels. The task is to turn it into a single-level list, in place, and return the head.
In the example, the top level is 1, 2, 3, 4, 5, 6. Node 3 has a child list 7, 8, 9, 10, and node 8 has a child list 11, 12. Each child list is spliced in right after its parent, before the parent's old successor. The result reads 1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6. After flattening, every child is nil and every prev link matches the next links.
The statement asks for a recursive algorithm that runs in O(n) time.
Approach: flatten the sub-list first, then splice it in
Walk along one level. Most nodes have no child, and the walk moves on. When a node has a child, it needs three things:
- The rest of the level after the node must not get lost, so save
node.next. - The child list must be flat before it is spliced in. That is the same problem on a smaller list, so the code calls itself on the child.
- The flat child list goes between the node and the saved successor. The node's
nextbecomes the child, and the last node of the child list gets the saved successor as itsnext.
To connect the end of the child list, the code needs to know which node is last. So the recursive helper returns the tail of the level it flattened. The caller keeps it as childTail and uses it for the reconnection.
After the splice, the walk continues with node.next, which is now the first child node. The walk therefore goes through the spliced nodes too, and finishes on the true last node of the level, which becomes the tail to return.
Step by step
- Delegate to a helper.
flattencallsflattenLevel(head)and returnshead. Flattening only rewires links, so the first node is still first. - Declare
flattenLevelaboveflatten. It takes aNode?and returns aNode?. The attribute@discardableResulttells the compiler that ignoring the returned tail is fine, whichflattendoes. - Make a mutable copy of the parameter.
var node = nodeshadows the constant parameter. Another variable,tail, starts equal to it and tracks the last node seen. For an empty level the loop never runs and the helper returnsnil. - Loop while
node != nil. Every node of this level is visited. - Test for a child with
node!.child != nil. Only these nodes need rewiring. - Save the successor in
next. - Flatten the child recursively and keep its tail in
childTail. - Link the node and its child in both directions:
node!.next = node!.childandnode!.child!.prev = node. - Clear
node!.child, so the flat list has no child links. This must come after the two lines above, which still read it. - Link the end of the child list to the saved successor:
childTail!.next = next. Ifnextexists, also setnext!.prev = childTail. If the node was the last on its level, there is nothing to point back. - Record and advance. After the
if, settail = nodeandnode = node!.next. - Return
tailafter the loop.
The solution in Swift
class Solution {
@discardableResult
func flattenLevel(_ node: Node?) -> Node? {
var node = node
var tail = node
while node != nil {
if node!.child != nil {
let next = node!.next
let childTail = flattenLevel(node!.child)
node!.next = node!.child
node!.child!.prev = node
node!.child = nil
childTail!.next = next
if next != nil {
next!.prev = childTail
}
}
tail = node
node = node!.next
}
return tail
}
func flatten(_ head: Node?) -> Node? {
flattenLevel(head)
return head
}
}
Swift details to notice:
@discardableResult. Without it, Swift warns that the result offlattenLevel(head)is unused. The attribute is a promise that ignoring the value is normal. The recursive call, which does use the value, is unaffected.- Shadowing a parameter. Function parameters are constants.
var node = nodecreates a new local variable with the same name, initialised from the parameter. It is the usual way to get a mutable copy. - Nodes are class instances.
node!.next = ...changes the actual node that other variables refer to, which is what in-place flattening needs. - Every
!has a reason.node!is safe inside the loop because the condition checked it.childTail!is safe because a child list has at least one node, so its tail exists.
Complexity
Time. Every node is spliced at most once and handled by the loop of its own level. In addition, the walk of a level continues over the nodes that were just spliced in, so a node is looked at again by each level above it. For a shallow structure this is close to O(n). For deep nesting the extra visits add up: a chain of 100 single-node levels makes 5,050 visits for 100 nodes. The exact bound is O(n * depth).
Space: O(depth). There is one stack frame per level of nesting, and nothing else is allocated. A very deep structure could exhaust the call stack.
Edge cases and common mistakes
- Empty list.
flatten(nil)returnsnil, because the loop never runs. - No children. The list is returned unchanged.
- A child on the last node of a level.
nextisnil, sochildTail!.nextbecomesniland the back link is skipped. The list1, 2with a child3, 4on node 2 becomes1, 2, 3, 4. - A child on the head. The head stays the head:
1, 2with a child3on node 1 becomes1, 3, 2. - Forgetting to clear
child. The list would look flat when read withnext, but each spliced parent would still point at the child list. - Forgetting the
prevlinks. Reading forward works, but walking backward from the end breaks. - Losing the successor. If
nextis read afternode!.nextis overwritten, the rest of the level is lost.
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.
