430. Flatten a Multilevel Doubly Linked List

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:

// Iteration
Node* flatten(Node* head) { // time: O(n); space: O(1)
    if (!head) return nullptr;
    Node* p = head;
    while (p) {
        // no child
        if (!p->child) {
            p = p->next;
            continue;
        }
        // has child
        Node* tmp = p->child;
        // connect the tail of child to the next p
        while (tmp->next) {
            tmp = tmp->next;
        }
        tmp->next = p->next;
        if (p->next) p->next->prev = tmp;
        // connect p to p->child and remove p->child
        p->next = p->child;
        p->child->prev = p;
        p->child = nullptr;
    }
    return head;
}

// Iteration
Node* flatten(Node* head) { // time: O(n); space: O(1)
    Node* cur = head;
    while (cur) {
        if (cur->child) {
            Node* next = cur->next;
            Node* last = cur->child;
            while (last->next) {
                last = last->next;
            }
            cur->next = cur->child;
            cur->next->prev = cur;
            cur->child = nullptr;
            last->next = next;
            if (next) next->prev = last;
        }
        cur = cur->next;
    }
    return head;
}

// Recursion
Node* flatten(Node* head) { // time: O(n); space: O(n)
    Node* cur = head;
    while (cur) {
        if (cur->child) {
            Node* next = cur->next;
            cur->child = flatten(cur->child);
            Node* last = cur->child;
            while (last->next) last = last->next;
            cur->next = cur->child;
            cur->next->prev = cur;
            cur->child = nullptr;
            last->next = next;
            if (next) next->prev = last;
        }
        cur = cur->next;
    }
    return head;
}