After flattening the multilevel linked list it becomes:
Problem overview
The function flatten receives head, the first node of a doubly linked list whose nodes are *Node values with Val, Prev, Next and Child fields. A node's Child may point to the head of a separate doubly linked list, and nodes in that list can have children of their own. The task is to flatten everything into one single-level doubly linked list, in place, and return its head.
The order is depth first: a child list goes right after its parent and before the parent's old next node. In the first example the levels are 1-2-3-4-5-6, with node 3 having the child list 7-8-9-10, and node 8 having the child list 11-12. The flattened list is [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]. For 1-2 where node 1 has the child 3, the answer is [1, 3, 2]. An empty list stays empty.
The statement asks for a recursive algorithm that runs in O(n) time.
Approach: flatten a level and report its tail
Splicing a child list into its parent's level takes four pieces: the parent, the parent's old next node, the child list's head and the child list's last node. The child's head is simply node.Child. The old next node is saved before any link changes. The missing piece is the last node of the flattened child list, and that is where the recursion helps.
Define a helper, flattenLevel(node), that flattens the list starting at node in place and returns its tail, the last node of the flattened result. To flatten a child list, call the same helper on node.Child. The call flattens that child list completely, including all of its own descendants, and returns the node that must be connected to the saved next.
The helper walks its level node by node. When a node has a child, it splices the flattened child in and then keeps walking with node = node.Next. After the splice, node.Next is the child list, so the walk goes through the spliced nodes and then continues with the rest of the original level. The helper remembers the last node it visited, and that is the tail it returns.
Take 1-2 with node 1 having the child 3. At node 1: save next = node 2, flatten the child (the tail is node 3), link 1 to 3, set 3's Prev to 1, clear 1's Child, link 3's Next to node 2, and set node 2's Prev to node 3. The walk then visits 3 and 2, and the result is 1-3-2.
Step by step
- Call
flattenLevel(head)fromflatten. The helper rewires pointers in place, so its returned tail is not needed here. - Return
head. Flattening never moves the first node, so it is still the head. - In
flattenLevel, settail := nodeand returntailat the end. For anilargument the loop never runs and the helper returnsnil, which handles an empty list. - Loop while
node != nil. Go writeswhileas aforwith only a condition. - Check for a child:
if node.Child != nil. Nodes without one need no rewiring. - Save
node.Nextinnextbefore it's overwritten, otherwise the rest of the level is unreachable. - Flatten the child recursively and keep the returned tail in
childTail. - Link the child list after the node:
node.Next = node.Child. - Repair the backward direction and clear the child.
node.Child.Prev = nodemust come first, becausenode.Child = nilremoves the pointer it reads. - Attach the saved
nextafterchildTail:childTail.Next = next. This works even whennextisnil. - Fix
next.Prev, but only ifnext != nil. Writing to a field of anilpointer panics. - Record the last visited node with
tail = node, then advance withnode = node.Next. After a splice, the walk continues through the child nodes, sotailends on the true last node of the whole flattened level.
The solution in Go
func flatten(head *Node) *Node {
flattenLevel(head)
return head
}
func flattenLevel(node *Node) *Node {
tail := node
for node != nil {
if node.Child != nil {
next := node.Next
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
}
Go details worth knowing:
- Ignoring a return value. A call such as
flattenLevel(head)can be used as a statement and its result discarded. Go requires explicit use only for variables and imports, not for return values. - Recursion on structs.
Nodecontains pointers toNode, which Go allows. Each recursive call has its ownnode,tail,nextandchildTail. - The parameter is reused as the cursor. The loop assigns to
node, which is only the function's local copy of the pointer, so the caller's variable is unaffected. This is whytailwas saved from the original value. - Nil safety. The two
nilcases are an empty list (handled by the loop condition) and a last node on its level (handled byif next != nil). AssigningchildTail.Next = nextwith anilnextis fine.
Complexity
Time: O(n) when nesting is shallow, O(n * d) in the worst case, where d is the deepest level of nesting. Splicing a child costs a constant number of assignments, but the walk of the parent's level then moves through the nodes that the recursive call has just flattened, so a node is visited once for its own level and once more for each ancestor level that walks over it. Those later visits only find that Child is already nil. In the worst case, a chain where every node is the only child of the previous one, the number of visits grows like n * (n + 1) / 2: 55 visits for 10 nodes, 5,050 for 100 and 500,500 for 1,000.
Space: O(d). The only extra memory is the recursion stack, one frame for each level of children being flattened. For that same chain, d is n.
Edge cases and common mistakes
- Empty list.
flatten(nil)returnsnil. - No children at all. The list is only traversed and returned unchanged.
- A child on the last node of a level. Here
nextisnil. Skipping thenext != nilcheck panics with a nil pointer dereference. - Forgetting to clear
Child. The list would look flat when read throughNextbut would still carry child links, so it isn't really single-level. - Not repairing
Prev. The forward direction would be right while walking backwards from the end gives a wrong order, becausechild.Prevandnext.Prevstill hold their old values. - Losing the old next node. Assigning
node.Next = node.Childbefore savingnextmakes the rest of the level unreachable. - Wrong tail. The tail of a flattened level isn't always the old last node of that level, because a child list may have been spliced in after it. The helper therefore tracks the last node actually visited.
Testing
- The three-level example gives
[1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6], with every node'sPrevmatching its predecessor and noChildleft. 1-2where node 1 has the child3gives[1, 3, 2].- An empty list gives an empty list.