Bloomberg 多级链表扁平化：只有 next/child 的 DFS 顺序

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 链表是有限无环结构，每个节点只属于一个位置，child 子链完整展平后才访问原 next。
• 训练版原地重接节点，返回 head，所有 child 置空；不复制值或创建新业务节点。

解题路线

1. 用显式栈模拟 DFS 前序。弹出当前 node 时，先压旧 next 再压 child，因此下一次先访问 child。
2. 把 node.child 与 node.next 旧连接清掉，再用 tail.next 接到展平链尾；原对象身份保持不变。
3. 若用递归，应返回子链尾以接回原 next；递归深度 D 很大时有栈溢出风险。
4. 验证展平后的节点序列等于递归参考顺序、每节点只出现一次、child 全空。

手动走一遍

1→2→3，节点 2 的 child 为 4→5：访问顺序 1,2,4,5,3；若先把 next=3 覆盖掉却没保存，就丢掉原主链尾部。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Node:
    def __init__(self, value, next=None, child=None):
        self.value = value
        self.next = next
        self.child = child


def flatten(head):
    """DFS preorder: node, full child chain, then saved next chain."""
    if head is None:
        return None
    stack = [head]
    dummy = Node(None)
    tail = dummy
    while stack:
        node = stack.pop()
        if node.next is not None:
            stack.append(node.next)
        if node.child is not None:
            stack.append(node.child)
        node.child = None
        node.next = None
        tail.next = node
        tail = node
    return dummy.next

复杂度

每节点压/弹一次，时间 O(n)，显式栈最坏 O(n)，在嵌套深度较浅且分支有限时通常更小；原地重接不复制节点。

易错点与追问

容易失分的边界

• 按值重建新节点，破坏调用方引用。
• 处理 child 前没保存 next。
• 留下 child 指针，形成多入口/潜在重复遍历。
• 直接套双向链表 LC430 而访问不存在的 prev。

继续深挖

• 递归方案尾节点怎样回传？
• 输入有环如何检测？
• 若需要恢复原多级结构要保留什么元数据？