题目链接：LeetCode 430. Faltten a Multilevel Doubly Linked List

class Node {

public:

    int val = NULL;

    Node* prev = NULL;

    Node* next = NULL;

    Node* child = NULL;

    Node() {}

    Node(int _val, Node* _prev, Node* _next, Node* _child) {

        val = _val;

        prev = _prev;

        next = _next;

        child = _child;

    }

};

class Solution {

public:

    // 解法一：迭代

    Node* flatten_iteration(Node *head) {

        if (head == NULL) {

            return NULL;

        }

        for (Node *p = head; p != NULL; p = p->next) {

            Node *next = p->next;

            if (p->child != NULL) {

                p->next = p->child;

                p->child->prev = p;

                p->child = NULL;

                Node *tmp = p->next;

                while (tmp->next != NULL) {

                    tmp = tmp->next;

                }

                tmp->next = next;

                next->prev = tmp;

            }

        }

        return head;

    }

    // 解法二：递归

    Node* flatten_recursion(Node *head) {

        if (head == NULL) {

            return head;

        }

        Node *p = head;

        while (p != NULL) {

            if (p->child != NULL) {

                Node *next = p->next;

                Node *nextLayer = flatten_recursion(p->child);

                p->next = nextLayer;

                nextLayer->prev = p;

                p->child = NULL;

                while (nextLayer->next != NULL) {

                    nextLayer = nextLayer->next;

                }

                nextLayer->next = next;

                if (next != NULL) {

                    next->prev = nextLayer;

                }

            }

            p = p->next;

        }

        return head;

    }

};