扁平化多级双向链表 图解题解

这道题到底在问什么

输入

主链 1-2-3,2.child=4-5

输出

1-2-4-5-3

输入

单节点 1,1.child=2-3

输出

1-2-3

最优解：一步一步想明白

1. 3记住"遇 child 就把整条子链拉平、塞进当前节点和它的 next 之间",下面逐帧套它。
2. 4开演前先看清结构:主链是 1↔2↔3,只有 3 个节点;但 2 身上挂着 child 子链 4↔5,4 又挂着 child 6。DFS 还没开始,先把整体盘一遍。
3. 5正式开始:读指针从头节点 1 出发,先 examine:看 1 有没有 child。
4. 6settle:节点 1 没有 child,本身已经就位。父层执行 cur = nxt 往后走,1 标记为已定型(蓝)。
5. 7examine 节点 2:它挂着一条 child 子链 4↔5。先把 2 原来的后继 nxt = 3 用变量记住,免得一会儿接子链时把它弄丢。
6. 82 的子链本身也是多级链,可能还带更深的 child,不能直接搬。settle 这一步先递归进 2 的子链去彻底拉平,主链 2 这里挂起等子链结果。
7. 9进到 2 的子链:4↔5,读指针从头节点 4 出发。examine 4:它又挂着一条 child 子链 6。
8. 10settle:4 有 child,先记住它的后继 nxt = 5,再往下递归一层去拉平 4 的子链。
9. 11进到 4 的子链:只有一个节点 6。examine 6:它没有 child,是最深一层。
10. 12settle:这一层不用再拆,直接返回。这条子链的头和尾都是 6,把尾 6 带回上一层。
11. 13回到 4 这层做插入手术第一步:4.next 接到子链头 6、6.prev 接 4、4.child 清空。现在 4 后面挂上了 6。注意 4 原来的后继 5 这时还悬着没接回来(图里 6 和 5 之间是断开的点,5 标灰表示待接回),下一帧再补上。
12. 14插入手术第二步:子链尾 tail 是 6,4 原来的后继是 5,所以现在把 6.next 接回 5、5.prev 接 6,断开的点变回箭头。这一层就拉平成 4↔6↔5。
13. 15父层执行 cur = nxt 回到 5。examine 5:它没有 child,settle 直接定型,这一层走完,返回尾节点 5。
14. 162 的整条子链现在彻底拉平成单层:4↔6↔5,尾节点是 5。这就是递归带回来的结果,可以拿去插进主链了。
15. 17带着拉平好的子链 4↔6↔5 回到主链 2 这层。examine:目标是把子链塞进 2 和它的后继 3 之间。
16. 18插入手术第一步:2.next 接到子链头 4、4.prev 接 2、2.child 清空。此刻 2 后面接上了 4↔6↔5。刚才记下的原后继 3 还等着接回来。
17. 19插入手术第二步:cur 仍是节点 2,子链尾 tail 是 5。把 5.next 接回原后继 3、3.prev 接 5。3 又重新挂到了子链尾后面,2 这层就接好了:1↔2↔4↔6↔5↔3。
18. 20子链 4、6、5 是在递归子调用里就处理并清空 child 的,父层不再逐个扫它们。父层执行 cur = nxt 直接回到原后继 3。examine 3:它没有 child。
19. 21settle 节点 3:没有 child 直接定型,它的 next 为空,主链这一层结束。整条链已是单层、再没有任何 child。
20. 22验证一下双向是否接对:从尾节点 3 沿 prev 往回走,3.prev = 5、5.prev = 6、6.prev = 4、4.prev = 2、2.prev = 1,一路顺到头,说明每处的 prev 都修对了,没有断链。
21. 23扁平化完成:单层双向链表 1↔2↔4↔6↔5↔3,所有 child 都已置空。回头看,我们就是一路 DFS,遇到 child 就把整条子链拉平、塞进当前节点和它后继之间,深的子链靠递归先拉平,一遍走完。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        def dfs(node):
            cur = node
            last = node
            while cur:
                nxt = cur.next
                if cur.child:
                    child_head = cur.child
                    child_tail = dfs(child_head)
                    cur.next = child_head
                    child_head.prev = cur
                    cur.child = None
                    if nxt:
                        child_tail.next = nxt
                        nxt.prev = child_tail
                    last = child_tail
                else:
                    last = cur
                cur = nxt
            return last
        if head:
            dfs(head)
        return head

using namespace std;
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
    Node(int _val) : val(_val), prev(nullptr), next(nullptr), child(nullptr) {}
};
class Solution {
public:
    Node* flatten(Node* head) {
        if (head) dfs(head);
        return head;
    }
    Node* dfs(Node* node) {
        Node* cur = node;
        Node* last = node;
        while (cur) {
            Node* nxt = cur->next;
            if (cur->child) {
                Node* childHead = cur->child;
                Node* childTail = dfs(childHead);
                cur->next = childHead;
                childHead->prev = cur;
                cur->child = nullptr;
                if (nxt) {
                    childTail->next = nxt;
                    nxt->prev = childTail;
                }
                last = childTail;
            } else {
                last = cur;
            }
            cur = nxt;
        }
        return last;
    }
};

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
    public Node(int _val) { val = _val; }
}
class Solution {
    public Node flatten(Node head) {
        if (head != null) dfs(head);
        return head;
    }
    private Node dfs(Node node) {
        Node cur = node, last = node;
        while (cur != null) {
            Node next = cur.next;
            if (cur.child != null) {
                Node childHead = cur.child;
                Node childTail = dfs(childHead);
                cur.next = childHead;
                childHead.prev = cur;
                cur.child = null;
                if (next != null) {
                    childTail.next = next;
                    next.prev = childTail;
                }
                last = childTail;
            } else {
                last = cur;
            }
            cur = next;
        }
        return last;
    }
}

复杂度

面试官可能追问