扁平化多级双向链表

难度: Medium

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：



扁平化后的链表如下图：

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

  1---2---NULL
  |
  3---NULL

示例 3：

输入：head = []
输出：[]

如何表示测试用例中的多级链表？

以 示例 1 为例：

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

序列化其中的每一级之后：

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

节点数目不超过 1000
1 <= Node.val <= 10^5

注意：本题与主站 430 题相同： https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/

Submission

运行时间: 25 ms

内存: 16.7 MB

"""
# 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: 'Node') -> 'Node':
        stash = []

        dummy = Node()
        dummy.next = head
        prev = dummy
        while head:
            if head.child is not None:
                if head.next is not None:
                    head.next.prev = None
                    stash.append(head.next)
                head.next = head.child
                head.child.prev = head
                head.child = None
                head = head.next
                prev = prev.next
            else:
                if head.next is None:
                    if len(stash) > 0:
                        head.next = stash.pop(len(stash)-1)
                head = head.next
                prev = prev.next
                if head is not None and head.prev is None:
                    head.prev = prev
        return dummy.next

Explain

题解采用的是深度优先遍历（DFS）的迭代实现，利用栈（在代码中是stash列表）来管理还未完全扁平化的节点。首先创建一个虚拟头节点dummy来简化边界条件处理，然后使用一个循环遍历所有节点。对于每个节点，如果它具有子节点，将其子节点插入到当前节点的下一个位置，并将原来的next节点压入栈中。如果当前节点没有next节点，且栈中还有节点，从栈中弹出一个节点作为next节点。继续这个过程，直到所有节点都被遍历完，从而实现链表的完全扁平化。

时间复杂度: O(n)

空间复杂度: O(n)

"""
# 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: 'Node') -> 'Node':
        stash = []  # 栈用来保存未处理的next节点

        dummy = Node(0, None, head, None) # 创建虚拟头节点以简化操作
        prev = dummy
        while head:
            if head.child is not None: # 当前节点有子节点
                if head.next is not None: # 保留当前节点的next节点
                    head.next.prev = None
                    stash.append(head.next)
                head.next = head.child # 将子节点接到当前节点的next上
                head.child.prev = head
                head.child = None
                head = head.next
                prev = prev.next
            else:
                if head.next is None and len(stash) > 0: # 当前节点无next，但栈非空
                    head.next = stash.pop() # 从栈中取出节点连接为next
                head = head.next
                prev = prev.next
                if head is not None and head.prev is None: # 确保prev节点正确
                    head.prev = prev
        return dummy.next
"""

Explore

在扁平化多级双向链表时，使用栈（DFS）可以更自然地维护链表的顺序。DFS策略优先深入到最内层的子链表并完成其扁平化，这符合多级链表扁平化的直观顺序，即优先处理当前节点的子节点直到其结束，然后再回到上一级节点的next节点。这种方式确保了处理流程的连续性和顺序性，使得扁平化后的链表能够保持正确的顺序。相比之下，使用队列（BFS）会导致先广泛地处理同一层的所有节点，这不符合直观的顺序要求，可能需要额外的操作来重新调整节点的顺序，从而增加了复杂度。

在将子节点接入为当前节点的下一个节点时，题解中首先检查当前节点是否有next节点。如果存在，这个原本的next节点会被保存到栈中。这样做确保了在子节点和它的所有后续节点被完全处理并扁平化后，可以从栈中恢复这个next节点，接在已扁平化部分的末尾。这种方法保证了原本的next节点不会丢失，并且可以在适当的时候重新链接到链表的正确位置。

使用虚拟头节点（dummy node）主要优点是简化了链表操作中的边界条件处理。通过引入一个虚拟的头节点，可以避免在处理原始链表头部是空的情况下的特殊判断，同时在链表前端的操作中不需要额外的条件来处理头节点可能变化的情况。虚拟头节点作为一个稳定的前置节点，确保了无论如何操作，返回的始终是dummy.next，从而简化了代码逻辑并提高了代码的可读性和健壮性。