LeetCode-430. 扁平化多级双向链表-题解
题目链接
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 = val
self.prev = prev
self.next = next
self.child = child
"""
def flattenList(head) :
if not head :
return head
tmp = head
while tmp :
if tmp.child :
phead = tmp.child
ptail = flattenList(phead)
ptail.next = tmp.next
if tmp.next :
tmp.next.prev = ptail
tmp.next = phead
phead.prev = tmp
tmp.child = None
tmp = tmp.next
while head and head.next :
head = head.next
return head
class Solution:
def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head :
return head
flattenList(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 = val
self.prev = prev
self.next = next
self.child = child
"""
class Solution:
def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head :
return None
stack = []
curr = head
while curr :
if curr.child :
if curr.next :
stack.append(curr.next)
curr.next = curr.child
curr.child.prev = curr
curr.child = None
if not curr.next and stack :
curr.next = stack.pop()
curr.next.prev = curr
curr = curr.next
return head