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:

方法1: dfs （post order）

思路：

用后序遍历的方法，先保证child 和next都已经是单链，这里next和child都有可能是null，要谨慎检查access。那么如果child不是空的话，我们就遍历到最后一个节点end，1. 将其连接到next上，并且如果next不是null，将next的prev连回end，2. 将child转移到head -> next，并将它的prev连回head（这里不用检查null是因为进入循环已经保证child一定非空），3. child设为null。最后返回修改后的head。

/*
// 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) {
        if (!head) return head;
        head -> child = flatten(head -> child);
        head -> next = flatten(head -> next);
        Node* end = head -> child;
        if (end){
            while (end -> next) {
                end = end -> next;
            }
            end -> next = head -> next;
            if (end -> next) end -> next -> prev = end;
            head -> next = head -> child;
            head -> next -> prev = head;
            head -> child = nullptr;
        }
        return head;
    }
};

方法2:

思路：

下面这个方法只对child进行了调用，并且仅对cur -> child非空的节点调用，在处理完当前cur的child之后，继续遍历直至结束。

/*
// 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* 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 = last;
            }
            cur = cur -> next;
        }
        return head;
    }
};