Start learning free

LESSON 277 OF 338 · LINKED LISTS

Flatten a Multilevel Doubly Linked List in Go: Iterative, O(n)

Practice O(n) Read the full explanation

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:



After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:

The input multilevel linked list is as follows:

  1---2---NULL
  |
  3---NULL

Example 3:

Input: head = []
Output: []

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Note:

Your algorithm should be iterative (non-recursive) and run in O(n) time.

STEP 1 OF 16

Guided

Ctrl + Enter to check

GO · LINKED LISTS

Flatten Multilevel List in Go, explained

Problem overview

The function flatten receives head, the first node of a doubly linked list made of *Node values with Val, Prev, Next and Child fields. A node's Child can point to the head of another doubly linked list, whose nodes may have children too. The function must flatten all levels into one doubly linked list, in place, and return its head. A child list goes right after its parent and before the parent's old next node.

For the levels 1-2-3-4-5-6, 7-8-9-10 (the child of node 3) and 11-12 (the child of node 8), the result 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]. An empty list stays empty.

This version must be iterative, with no recursion, and run in O(n) time.

Approach: splice children in as the walk reaches them

A recursive solution flattens each child before splicing it. The iterative version needs no recursion because of one observation: splicing a child list into the current level does not need that child list to be flat yet. If the child list still has children of its own, they can be spliced later, when the walk reaches them.

So the code makes one walk with a single cursor, node. At each node:

If the node has no child, move on to node.Next.
If it has a child, put the whole child list between node and its old next node, then move on to node.Next, which is now the head of the child list.

Because the walk then goes through the child list's nodes, any child of those nodes is spliced in when the walk gets there. Deeper levels get flattened one after another, using the same loop. For the three-level example, the walk reaches node 3 and inserts 7-8-9-10 before 4. Later, at node 8, it inserts 11-12 between 8 and 9, and the list becomes the expected order.

The splice needs the last node of the child's own level, so it can be connected to the saved next node. A small helper, getTail, finds it by following Next to the end. It runs only on the child's own level, which hasn't been spliced yet, so it never walks into a deeper level.

Step by step

Start a cursor, node := head. The head itself must not move, because it is the return value.
Loop while node != nil, so every node of the growing list is visited.
Check for a child: if node.Child != nil.
Save node.Next in next. The splice overwrites that link.
Find the child level's last node with childTail := getTail(node.Child).
Link the child after the node: node.Next = node.Child.
Point the child's Prev at the node: node.Child.Prev = node. It comes before the next step, because that step erases the pointer this one reads.
Clear the child: node.Child = nil. Flattened nodes keep no child links.
Reattach the rest of the level: childTail.Next = next. A nil value is fine if the node was last on its level.
Repair next.Prev to childTail, guarded by if next != nil.
Advance: node = node.Next, outside the if. After a splice this enters the child list, which is how nested levels get flattened.
Return head. The first node never changes. Returning node would give nil, because the loop ends when it becomes nil.
Write getTail: while node.Next != nil, set node = node.Next; then return node. It stops on the last node, not on the nil after it.

The solution in Go

func flatten(head *Node) *Node {
	node := head
	for node != nil {
		if node.Child != nil {
			next := node.Next
			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
}
func getTail(node *Node) *Node {
	for node.Next != nil {
		node = node.Next
	}
	return node
}

Go details worth knowing:

Parameters are local copies. In getTail, node = node.Next moves only the function's own pointer. The caller's node.Child is unchanged, so the caller still has the head of the child list after the call.
No nil check in getTail. It is only called inside if node.Child != nil, so its argument is never nil. Calling it with nil would panic with a nil pointer dereference at node.Next.
Declaration order doesn't matter. flatten calls getTail, which is defined below it. Go resolves package-level functions no matter where they appear.
Short-lived variables. next and childTail are declared inside the if block, so they exist only for that splice, and a fresh pair is created each time.

Complexity

Time: O(n). The main loop visits every node once, because each node is spliced in once and then walked over once. getTail walks the child's own level once, and a node belongs to exactly one level's tail search, since the search happens before deeper levels are merged in. So each node is touched a constant number of times.

Space: O(1). There is no recursion and no stack or queue, only a few pointers.

Compared with the recursive lesson, this version has the same O(n) bound without needing stack space proportional to the nesting depth.

Edge cases and common mistakes

Empty list. With head == nil the loop doesn't run, and the function returns nil.
A child on the last node. Then next is nil. Setting childTail.Next = nil is fine, but next.Prev would panic, hence the guard.
Child lists with children. The walk continues into the spliced nodes, so a child's child is handled when the walk reaches its parent. Moving to the old next node instead would skip this.
Clearing Child too early. If node.Child = nil comes before node.Child.Prev = node, the second line dereferences nil and panics.
Not saving next. After node.Next = node.Child, the old next node is no longer reachable.
Leaving stale Prev pointers. The forward order can be right while the backward links still point at the old neighbours.
Returning node. After the loop it is nil.

Testing

The three-level example gives [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6], with each Prev correct and no Child left.
1-2 where node 1 has the child 3 gives [1, 3, 2].
An empty list gives an empty list.

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free