文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Flatten a Multilevel Doubly Linked List

2. Solution

/*
// Definition for a Node.
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(Node* head) {
        stack<Node*> nodes;
        Node* current = head;
        Node* pre = nullptr;
        while(current) {
            if(current->child) {
                if(current->next) {
                    nodes.push(current->next);
                }
                current->next = current->child;
                current->next->prev = current;
                current->child = nullptr;
            }
            pre = current;
            current = current->next;
            if(!current && !nodes.empty()) {
                Node* temp = nodes.top();
                nodes.pop();
                pre->next = temp;
                temp->prev = pre;
                current = temp;
            }
        }
        return head;    
    }
};

Reference

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