TikTok 多层双链表扁平化：DFS 顺序与原地拼接

题意与假设

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

• 训练节点有 prev/next/child，child 与 next 构成无环、不共享节点的层次；头 prev=None。
• 顺序为当前节点、完整 child、原 next。没有指定顺序时先确认；所有 child 最终清空。

解题路线

1. 栈版保存原 next，再走 child，自然得到深度优先顺序；重点是复用节点身份并修复反向链接，而不是仅输出值。
2. 空间优化在遇 child 时先找其当前横向链尾，把原 next 接到尾部，再把 child 头接为当前 next，清空 child；随后沿 next 继续，会在将来处理更深 child。
3. 找尾扫描的是该层原本的横向边，先拼接祖先 continuation 再访问其内部时，扫描子链仍只覆盖该子层未拼接的边。每条原始横向边最多被尾扫描一次，再被主遍历一次，总体线性。
4. 每次拼接维护 child头.prev=当前、原next.prev=child尾、前向连接对称。不能漏掉空原next，也不能产生保留 child 的重复遍历路径。

手动走一遍

1.next=2、1.child=3、3.next=4、3.child=5，最终1,3,5,4,2，全部 child=None，逆向走为2,4,5,3,1。若结构共享节点或有环，本文算法不适用，先决定拒绝还是需要访问集。

Python 参考实现

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

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

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


def flatten(head):
    """Acyclic disjoint child/next structure; DFS child before original next.
    Mutates the existing nodes in O(n) time, O(1) auxiliary space."""
    node = head
    while node:
        if node.child:
            tail = node.child
            while tail.next:
                tail = tail.next
            following = node.next
            tail.next = following
            if following:
                following.prev = tail
            node.next = node.child
            node.child.prev = node
            node.child = None
        node = node.next
    return head

复杂度

n 节点 O(n) 时间、O(1) 额外空间，原地修改。栈版额外空间随层次或待续链数量增长，最坏 O(n)。

易错点与追问

容易失分的边界

• 只改 next 不改 prev。
• 把层序扁平化误成 DFS。
• 共享节点/环未定义仍声称可处理。

继续深挖

• 若必须不修改输入如何输出？
• 如何验证节点身份无遗漏无重复？