Leetcode 430: Flatten a Multilevel Doubly Linked List

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/

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:

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

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

Explanation for the above example:

Given the following multilevel doubly linked list:

We should return the following flattened doubly linked list:

Notes:

This is a high-frequency interview question.

There are a lot of ways to solve this problem, and here I want to share two of them.

One is recursive, the other is iterative. Both are pretty straightforward.

Let's look at the first one:

When we meet with a non-nullptr child note, we just run a flatten(child). If we can return the head and tail, then we can simply insert this flattened result into the previous position.

 See the code below:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;

    Node() {}

    Node(int _val, Node* _prev, Node* _next, Node* _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
public:
    Node* flatten(Node* head) {
        flat(head);
        return head;
    }
private:
    pair<Node*, Node*> flat(Node* head) {
      //  if(!head) return {head, head};
        Node* end = head;
        while(end) {
            Node* p = end->next;
            if(end->child) {
                auto res = flat(end->child);
                end->child = nullptr;
                end->next = res.first;
                res.first->prev = end;
                res.second->next = p;
                if(p) p->prev = res.second;
                else end = res.second;//must have
            }
            if(!p) break;
            end = p;
        }
        return {head, end};
    }
};

Now let us look at another method.

When we meet with a non-nullptr child, we just insert the next layer starting with the child note after the cur node position. Then continue the scan, and repeat the above process, done.

See the code below:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;

    Node() {}

    Node(int _val, Node* _prev, Node* _next, Node* _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};

*/
class Solution {
public:
    Node* flatten(Node* head) {
        Node *p = head;
        while(p) {
            if(p->child) {
                Node* q = p->next;
                p->next = p->child;
                p->child->prev = p;
                p->child = nullptr;
                Node *r = p->next;
                while(r->next) r = r->next;
                r->next = q;
                if(q) q->prev = r;
            }
            p = p->next;
        }
        return head;
    }
};