文章作者：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;
}
};
