扁平化多级双向链表

记住"遇 child 就把整条子链拉平、塞进当前节点和它的 next 之间",下面逐帧套它。

开演前先看清结构:主链是 1↔2↔3,只有 3 个节点;但 2 身上挂着 child 子链 4↔5,4 又挂着 child 6。DFS 还没开始,先把整体盘一遍。

正式开始:读指针从头节点 1 出发,先 examine:看 1 有没有 child。

settle:节点 1 没有 child,本身已经就位。父层执行 cur = nxt 往后走,1 标记为已定型(蓝)。

examine 节点 2:它挂着一条 child 子链 4↔5。先把 2 原来的后继 nxt = 3 用变量记住,免得一会儿接子链时把它弄丢。

2 的子链本身也是多级链,可能还带更深的 child,不能直接搬。settle 这一步先递归进 2 的子链去彻底拉平,主链 2 这里挂起等子链结果。

进到 2 的子链:4↔5,读指针从头节点 4 出发。examine 4:它又挂着一条 child 子链 6。

settle:4 有 child,先记住它的后继 nxt = 5,再往下递归一层去拉平 4 的子链。

进到 4 的子链:只有一个节点 6。examine 6:它没有 child,是最深一层。

settle:这一层不用再拆,直接返回。这条子链的头和尾都是 6,把尾 6 带回上一层。

回到 4 这层做插入手术第一步:4.next 接到子链头 6、6.prev 接 4、4.child 清空。现在 4 后面挂上了 6。注意 4 原来的后继 5 这时还悬着没接回来(图里 6 和 5 之间是断开的点,5 标灰表示待接回),下一帧再补上。

插入手术第二步:子链尾 tail 是 6,4 原来的后继是 5,所以现在把 6.next 接回 5、5.prev 接 6,断开的点变回箭头。这一层就拉平成 4↔6↔5。

父层执行 cur = nxt 回到 5。examine 5:它没有 child,settle 直接定型,这一层走完,返回尾节点 5。

2 的整条子链现在彻底拉平成单层:4↔6↔5,尾节点是 5。这就是递归带回来的结果,可以拿去插进主链了。

带着拉平好的子链 4↔6↔5 回到主链 2 这层。examine:目标是把子链塞进 2 和它的后继 3 之间。

插入手术第一步:2.next 接到子链头 4、4.prev 接 2、2.child 清空。此刻 2 后面接上了 4↔6↔5。刚才记下的原后继 3 还等着接回来。

插入手术第二步:cur 仍是节点 2,子链尾 tail 是 5。把 5.next 接回原后继 3、3.prev 接 5。3 又重新挂到了子链尾后面,2 这层就接好了:1↔2↔4↔6↔5↔3。

子链 4、6、5 是在递归子调用里就处理并清空 child 的,父层不再逐个扫它们。父层执行 cur = nxt 直接回到原后继 3。examine 3:它没有 child。

settle 节点 3:没有 child 直接定型,它的 next 为空,主链这一层结束。整条链已是单层、再没有任何 child。

验证一下双向是否接对:从尾节点 3 沿 prev 往回走,3.prev = 5、5.prev = 6、6.prev = 4、4.prev = 2、2.prev = 1,一路顺到头,说明每处的 prev 都修对了,没有断链。

扁平化完成:单层双向链表 1↔2↔4↔6↔5↔3,所有 child 都已置空。回头看,我们就是一路 DFS,遇到 child 就把整条子链拉平、塞进当前节点和它后继之间,深的子链靠递归先拉平,一遍走完。

边界:无 child 原样返回、空链直接返回、深嵌套靠递归一层层拉平。

两个高频追问:可用显式栈迭代;顺序必须深度优先。