扁平化多级双向链表

标签: 深度优先搜索 链表 双向链表

难度: Medium

你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。

给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。

返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。

示例 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]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：

示例 3：

输入：head = []
输出：[]
说明：输入中可能存在空列表。

提示：

  • 节点数目不超过 1000
  • 1 <= Node.val <= 105

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

以 示例 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]

Submission

运行时间: 32 ms

内存: 16.1 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: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return head
        cur=dummy1=Node(next=head)
        # dummy1=Node()
        dummy2=cur2=None
        while cur.next or cur.child:

            if cur.child:
                # if not cur.next:
                    
                if not dummy2 and cur.next:
                    dummy2=cur.next
                    dummy2.prev=None
                elif cur.next:
                    tmp=dummy2
                    dummy2=cur2=cur.next

                    while cur2.next:
                        cur2=cur2.next
                    cur2.next=tmp
                    tmp.prev=cur2
                cur.next=cur.child
                cur.next.prev=cur
                cur.child=None
                cur=cur.next
            else:
                cur=cur.next
        if dummy2:
            cur.next,dummy2.prev=dummy2,cur
        return dummy1.next

Explain

该题解采用了迭代的方式来处理多级双向链表的扁平化。首先，创建一个虚拟头节点 `dummy1` 来简化边界条件的处理，并使得返回扁平化链表时更为方便。然后，使用一个指针 `cur` 从虚拟头节点开始遍历原始链表。对于每个节点，检查是否存在子节点： 1. 如果当前节点 `cur` 有子节点，将其子节点插入到 `cur` 和 `cur.next` 之间，并更新相应的指针。 2. 如果 `cur` 没有子节点，则直接移动到下一个节点。 3. 在将子链表插入后，原始的 `cur.next` 节点（如果存在的话）会被暂存起来，并在处理完所有子链表后，接在当前链表的末尾。 这种方法确保了所有子链表被逐一插入到正确的位置，最终实现整个链表的扁平化。

时间复杂度: O(n)

空间复杂度: O(1)

"""
# 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 head
        cur = dummy1 = Node(next=head)  # 创建一个虚拟头节点以简化边界处理
        dummy2 = cur2 = None # 用于处理原始cur.next的节点
        while cur.next or cur.child:
            if cur.child:
                if not dummy2 and cur.next:
                    dummy2 = cur.next
                    dummy2.prev = None
                elif cur.next:
                    tmp = dummy2
                    dummy2 = cur2 = cur.next
                    while cur2.next:  # 寻找当前链表的末尾
                        cur2 = cur2.next
                    cur2.next = tmp  # 将原始的next链表接在当前链表末尾
                    tmp.prev = cur2
                cur.next = cur.child  # 将子链表连接为当前节点的next
                cur.next.prev = cur  # 更新子链表的头节点的prev指针
                cur.child = None  # 清除当前节点的child指针，避免循环引用
                cur = cur.next
            else:
                cur = cur.next
        if dummy2:
            cur.next, dummy2.prev = dummy2, cur  # 将暂存的原始next链表接回到处理完的链表末尾
        return dummy1.next # 返回扁平化后的链表的头节点
        "

Explore

在处理子链表时，算法首先检查当前节点 `cur` 是否有子节点。如果有，它会将 `cur` 的子节点插入到 `cur` 和 `cur.next` 之间。这通过直接修改 `cur.next` 指向 `cur.child` 并同时更新 `cur.child.prev` 指向 `cur` 来完成。接着，原 `cur.next`（如果存在）会被暂存，并在子链表处理完后接回到链表的末端。这样确保了每个子链表都正确地插在其父节点之后。

是的，算法能够递归地处理多层子链表。这是通过在遍历链表时，每遇到一个有子节点的节点，就先处理该子链表，然后再继续处理原始链表的下一个节点。这个过程会一直重复，直到所有可能的子链表都被处理完毕，确保了即使是多层子链表也能被完全扁平化。

在重新连接原始的 `cur.next` 链表时，我确保在将子链表插入后，暂存原始的 `cur.next`。在处理完所有子链表后，我检查并确保 `cur.next` 是空（即当前链表的末尾），然后再将暂存的原始 `cur.next` 链表接回去，并更新相应的 `prev` 指针。这样的处理避免了循环引用的问题，因为我们通过逻辑保证每个节点只被访问一次，并且在连接时验证了链表的末端状态。