# Mikhail Kalashnikov

## Flatten a multilevel doubly linked list

This time we'll focus attention on the problem which goes as follow:

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.

It may sound intimidating while in reality it is pretty straightforward. The problem makes more sense if we take a look at the illustration.

What we need to return is a flat doubly linked list.

Intuitively, it feels like we need to insert the child subchain into our list, iterating over it at the same time. The trick is to carefully reassign the pointers to inject the subchain.

let flatten = (head) => {
for (let phead = head; phead; phead = phead.next) {
if (phead.child) {
let ctail = phead.child
while (ctail.next) { ctail = ctail.next }

if (phead.next) {
phead.next.prev = ctail
}

phead.child.prev = phead
ctail.next = phead.next
phead.next = phead.child

phead.child = null
}
}

return head
}


This picture should make it even more obvious.

Simple and fun! Check out the full code on github