LeetCode 题解工作台
扁平化多级双向链表
你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。 给定链表的头节点 head ，将链表 扁平化 ，以便所有…
3
题型
3
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
""" class Node:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。
给定链表的头节点 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]
解题思路
方法一
"""
# 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':
def preorder(pre, cur):
if cur is None:
return pre
cur.prev = pre
pre.next = cur
t = cur.next
tail = preorder(cur, cur.child)
cur.child = None
return preorder(tail, t)
if head is None:
return None
dummy = Node(0, None, head, None)
preorder(dummy, head)
dummy.next.prev = None
return dummy.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N), where N is the total number of nodes across all levels, because each node is visited once. Space complexity is O(D) for recursive DFS due to the call stack, where D is the maximum depth of nesting, or O(N) for iterative stack-based approaches in the worst case. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Clarify how to handle null child pointers and empty lists.
- question_mark
Expect you to traverse nodes in the correct flattened order using pointer manipulation.
- question_mark
Check that all child pointers are properly nullified and prev/next pointers remain consistent.
常见陷阱
外企场景- error
Forgetting to set child pointers to null after flattening, leading to dangling references.
- error
Misconnecting next and prev pointers when inserting child lists, which breaks the doubly linked structure.
- error
Using inefficient repeated scans instead of a DFS approach, causing higher time complexity.
进阶变体
外企场景- arrow_right_alt
Flatten a multilevel singly linked list where each node has only next and child pointers.
- arrow_right_alt
Flatten a tree-like linked list with arbitrary branching instead of strict next/child structure.
- arrow_right_alt
Flatten and reverse a multilevel doubly linked list in one pass, maintaining depth-first order.