After flattening the multilevel linked list it becomes:
Problem overview
The method flatten receives the head of a doubly linked list. Each Node has prev, next and child links, and a child may point to the head of another doubly linked list, which can have children of its own. The method must rewire the nodes in place so that everything sits on a single level, and return the head.
In the first 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. The flattened order is [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]: each child list goes right after its parent. With 1-2 and a child 3 under node 1, the result is [1, 3, 2]. An empty list stays empty.
Approach: splice as you walk, with no recursion
Walk the list with a single cursor. When the cursor is on a node with a child, splice the child list in between that node and its old successor. The cursor then moves to the next node, which is now the first node of the spliced child list. That is the key to avoiding recursion: if a node in the child list has a child of its own, the cursor reaches that node later and splices its child in the same way. Deeper levels are flattened when the walk gets to their parents, so nested levels disappear without any extra bookkeeping.
The splice needs the tail of the child list, the last node on the child's own level, because that is the node that must point to the saved successor. A small helper, getTail, finds it by following next until there is none. It only walks the child's own level, since deeper levels have not been spliced yet. Each node is walked by getTail at most once, so the whole job stays linear.
The lesson also has a recursive version, where the helper returns the tail of an already flattened child. This version keeps the work in one loop.
Step by step
- Create a walker.
var node = headmoves along the list.headstays unchanged because it is the return value. - Loop while
nodeis notnull, so every node is visited. - Check for a child. Nodes without one just let the loop move on.
- Save the successor in
val next = node.next. Oncenode.nextis overwritten with the child, the rest of the level would otherwise be unreachable. - Find the child list's tail with
val childTail = getTail(node.child). - Link the node to its child in both directions:
node.next = node.childandnode.child.prev = node. Both lines readnode.child, so they come before it is cleared. - Clear the child:
node.child = null. - Reconnect the rest with
childTail.next = next, and setnext.prev = childTailonly whennextis notnull. - Advance outside the
if:node = node.next. After a splice this is the first child node, so the loop walks through the spliced nodes and flattens nested levels. - Return
headafter the loop. Returningnodewould be wrong, since it isnullby then. - Write
getTailaboveflatten. It takes aNodeand returns one. - Walk to the last node. Copy the parameter into
var n, advance it whilen.next != null, and end withn. The test is onn.next, because the goal is the last node, not thenullafter it.
The solution in Scala
class Solution {
def getTail(node: Node): Node = {
var n = node
while (n.next != null) {
n = n.next
}
n
}
def flatten(head: Node): Node = {
var node = head
while (node != null) {
if (node.child != null) {
val next = node.next
val childTail = getTail(node.child)
node.next = node.child
node.child.prev = node
node.child = null
childTail.next = next
if (next != null) {
next.prev = childTail
}
}
node = node.next
}
head
}
}
The Scala details worth knowing:
- Method order.
getTailis defined beforeflattento match the lesson's steps, but inside a class the order does not matter to the compiler. - Parameters are immutable.
getTailcan't move itsnodeparameter, so it copies it intovar n. - The last expression is the value.
nandheadare the final lines of their methods and need noreturn. valinside a loop.nextandchildTailare declared withvalinside theifbody. Each pass through the body creates new ones, so they are not shared between iterations.nullchecks are explicit.getTailassumes its argument is notnull, which is safe because it is only called afternode.child != null. Calling it withnullwould throw aNullPointerException.
Complexity
Time: O(n), where n is the number of nodes. The main loop visits each node once. getTail walks the child list's own level before it is spliced, and a node is part of exactly one such walk, so those walks add at most another n steps.
Space: O(1). There is no recursion and no extra collection, only a few references. The list is changed in place.
Edge cases and common mistakes
- Empty list. The loop doesn't run and
nullis returned. - A child on the last node.
nextisnull, so the child list just becomes the end, and the null check prevents a crash. - Stopping
getTailone step too late. A loop onn != nullwould end withnull, andchildTail.next = nextwould then fail. - Moving the cursor inside the
if. Then nodes without a child would never advance the cursor, and the loop would not finish. - Skipping over the spliced nodes. Jumping to
nextafter a splice would skip the child nodes and leave their own children unflattened. - Leaving child pointers. Without
node.child = null, the list keeps stale children, and walking it again would splice the same lists in a second time. - Setting only
next. Both directions need updating, otherwise walking backward throughprevbreaks.
Testing
- The first example gives
[1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]. 1-2with a child3under node 1 gives[1, 3, 2].- An empty list gives an empty list.
1with a child2whose own child is3-4gives[1, 2, 3, 4].- Walking the flattened first example backward through
prevfrom the last node gives[6, 5, 4, 10, 9, 12, 11, 8, 7, 3, 2, 1].
