Flatten a multilevel doubly linked list

This time I want to focus your attention on this 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.