题目链接
430. 扁平化多级双向链表 - 力扣（LeetCode）
题目介绍
你将得到一个双链表，节点包含一个“下一个”指针、一个“前一个”指针和一个额外的“子指针”。这个子指针可能指向一个单独的双向链表，并且这些链表也包含类似的特殊节点。子列表可以有一个或多个自己的子列表，从而形成多层数据结构。
给定链表的头节点
head，需要将链表扁平化，使所有节点都出现在单层双链表中。对于带有子列表的节点curr，子列表中的节点应该位于扁平化列表中curr之后，以及curr.next之前。返回扁平化后的列表头
head，列表中的节点的所有子指针必须设置为null。
题目知识点
涉及到高级数据双向链表（主要考察点 - 修改指针指向模拟符合题目要求）
/*
// Definition for a Node.
class Node {
public:
int val;
Node* prev;
Node* next;
Node* child;
};
*/
题目示例
题目分析
我们通过题目可以清晰地了解到该题目的目的很简单，只是通过模拟来完成扁平化处理，那么对于题目而言是什么是扁平化呢，只有当包含有子指针时才会有扁平化操作，因此只是一个遍历当前节点并找到没有子指针结束的节点，不断的递归。（该方法的模拟在第二解中有所提示）
那么该题目还可以通过另一种方式来完成，这是一个重复的扁平化过程，含有子指针的双向链表的未结点会指向当前节点下一个节点，当前节点指向孩子节点的双向链表，重复扁平化处理双向链表即可，我们可以通过一个方法来模拟这个过程 // 传入一个头节点，返回一个扁平化后的未结点 //。
最后一种方式，是借助栈的特性（先进后出）用来模拟递归行为，栈可以帮助我们记录节点，先处理 child 链表，再处理 next 链表。当处理完 child 后，将 next 节点推入栈，以便之后继续处理。
代码示例：
Node* flattenList(Node* head)
{
Node *tmp = head ;
while (tmp)
{
if (tmp -> child)
{
Node *phead = tmp -> child ;
Node *ptail = flattenList(phead) ;
ptail -> next = tmp -> next ;
if (tmp -> next)
{
tmp -> next -> prev = ptail ;
}
tmp -> next = phead ;
phead -> prev = tmp ;
tmp -> child = nullptr ;
}
tmp = tmp -> next ;
}
tmp = head ;
while (tmp -> next) tmp = tmp -> next ;
return tmp ;
}
完整代码
// 方法二
class Solution {// 传入一个头节点，返回一个扁平化后的未结点Node* flattenList(Node* head){Node *tmp = head ;while (tmp){if (tmp -> child){Node *phead = tmp -> child ;Node *ptail = flattenList(phead) ;ptail -> next = tmp -> next ;if (tmp -> next){tmp -> next -> prev = ptail ;}tmp -> next = phead ;phead -> prev = tmp ;tmp -> child = nullptr ;}tmp = tmp -> next ;}tmp = head ;while (tmp -> next) tmp = tmp -> next ;return tmp ;}
public:Node* flatten(Node* head) {if (head == nullptr){return head;}flattenList(head) ; return head ; }
};
"""
# Definition for a Node.
class Node:def __init__(self, val, prev, next, child):self.val = valself.prev = prevself.next = nextself.child = child
"""
def flattenList(head) :if not head : return headtmp = headwhile tmp :if tmp.child : phead = tmp.childptail = flattenList(phead)ptail.next = tmp.nextif tmp.next : tmp.next.prev = ptailtmp.next = pheadphead.prev = tmptmp.child = Nonetmp = tmp.nextwhile head and head.next :head = head.nextreturn head
class Solution:def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':if not head :return headflattenList(head)return head// 方法三class Solution {
public:Node* flatten(Node* head) {if (!head) return nullptr ;stack <Node*> stack ;auto curr = head ;while (curr){if (curr -> child){if (curr -> next){stack.push(curr -> next) ;}curr -> next = curr -> child ;curr -> child -> prev = curr ;curr -> child = nullptr ;}if (!curr -> next && !stack.empty()){curr -> next = stack.top() ;stack.pop() ;curr -> next -> prev = curr ;}curr = curr -> next ;}return head ;}
}; 
# 方法三 - 栈（stack）python
"""
# Definition for a Node.
class Node:def __init__(self, val, prev, next, child):self.val = valself.prev = prevself.next = nextself.child = child
"""class Solution:def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':if not head :return Nonestack = []curr = headwhile curr :if curr.child :if curr.next :stack.append(curr.next)curr.next = curr.childcurr.child.prev = currcurr.child = Noneif not curr.next and stack :curr.next = stack.pop()curr.next.prev = currcurr = curr.nextreturn head
