430. 扁平化多级双向链表

题目描述

每个节点有三个指针：prev 指向前一个节点，next 指向后一个节点，child 可能指向另一条双向链表的头。那条子链表上的节点也可以再带自己的子链表，于是形成多层结构。

输入第一层的头节点 head。要求把整个结构展开成只有一层的双向链表：若节点 curr 有子链表，则把这条子链表（已经展开过的）整段插在 curr 与原来的 curr.next 之间。

展开后每个节点的 child 都必须设为空，prev 和 next 要正确相连。返回展开后链表的头节点；输入为空时返回空。

数组表示方式：逐层写出各层节点值，每层末尾补一个 null；下一层开头用若干 null 占位，使它的第一个节点对齐到上一层中拥有它的那个节点，最后删去末尾多余的 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]

解释：第一层是 1-2-3-4-5-6，节点 3 下挂 7-8-9-10，节点 8 下挂 11-12；逐层插入后得到输出序列。

示例 2

输入：head = [1,2,null,3]
输出：[1,3,2]

解释：节点 1 下挂子链 [3]，把 3 插到 1 和 2 之间。

示例 3

输入：head = []
输出：[]

解释：空链表直接返回空。

数据范围

节点总数不超过 1000。
1 <= Node.val <= 10^5

解题思路：迭代展开子链表

用 cur 沿 next 从头往后走。遇到有 child 的节点：先记下原后继 nxt；从 child 出发走到子链尾 tail；把 cur 与 child 双向相连并清空 child；再把 tail 与 nxt 双向相连。然后 cur 继续沿 next 前进——刚接入的子链会被依次访问，其中更深的子链也会用同样方法展开。

为什么正确

cur 之前（含 cur 已处理部分）的节点都已没有 child，并且从 head 到 cur 的 prev/next 双向一致。

复杂度分析

每个节点被 cur 访问一次，找尾时子链节点会被额外走过，最坏 O(n·d)（d 为层数），通常视为 O(n)；额外空间 O(1)。

易错点

双向链表要同时维护 prev：cur.child.prev = cur 和 nxt.prev = tail 都不能漏，nxt 为 None 时不能访问 nxt.prev。还要记得把 cur.child 置为 None，否则判题会认为没有扁平化。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        cur = head
        while cur:
            if cur.child:
                nxt = cur.next
                tail = cur.child
                while tail.next:
                    tail = tail.next
                cur.next = cur.child
                cur.child.prev = cur
                cur.child = None
                tail.next = nxt
                if nxt:
                    nxt.prev = tail
            cur = cur.next
        return head

class Solution {
    public Node flatten(Node head) {
        Node cur = head;
        while (cur != null) {
            if (cur.child != null) {
                Node nxt = cur.next;
                Node tail = cur.child;
                while (tail.next != null)
                    tail = tail.next;
                cur.next = cur.child;
                cur.child.prev = cur;
                cur.child = null;
                tail.next = nxt;
                if (nxt != null)
                    nxt.prev = tail;
            }
            cur = cur.next;
        }
        return head;
    }
}

class Solution {
public:
    Node* flatten(Node* head) {
        Node* cur = head;
        while (cur) {
            if (cur->child) {
                Node* nxt = cur->next;
                Node* tail = cur->child;
                while (tail->next)
                    tail = tail->next;
                cur->next = cur->child;
                cur->child->prev = cur;
                cur->child = nullptr;
                tail->next = nxt;
                if (nxt)
                    nxt->prev = tail;
            }
            cur = cur->next;
        }
        return head;
    }
};

func flatten(root *Node) *Node {
	cur := root
	for cur != nil {
		if cur.Child != nil {
			nxt := cur.Next
			tail := cur.Child
			for tail.Next != nil {
				tail = tail.Next
			}
			cur.Next = cur.Child
			cur.Child.Prev = cur
			cur.Child = nil
			tail.Next = nxt
			if nxt != nil {
				nxt.Prev = tail
			}
		}
		cur = cur.Next
	}
	return root
}

var flatten = function(head) {
    let cur = head;
    while (cur) {
        if (cur.child) {
            const nxt = cur.next;
            let tail = cur.child;
            while (tail.next)
                tail = tail.next;
            cur.next = cur.child;
            cur.child.prev = cur;
            cur.child = null;
            tail.next = nxt;
            if (nxt)
                nxt.prev = tail;
        }
        cur = cur.next;
    }
    return head;
};

function flatten(head: _Node | null): _Node | null {
    let cur = head;
    while (cur) {
        if (cur.child) {
            const nxt = cur.next;
            let tail: _Node = cur.child;
            while (tail.next)
                tail = tail.next;
            cur.next = cur.child;
            cur.child.prev = cur;
            cur.child = null;
            tail.next = nxt;
            if (nxt)
                nxt.prev = tail;
        }
        cur = cur.next;
    }
    return head;
};

载入编辑器，自己跑一遍 →

其他解法

迭代法不占额外空间，但每次都要走到子链表尾部；DFS 一次遍历并直接拿到尾节点，代价是递归栈。

解法 2：深度优先搜索时间 O(n)，空间 O(d)

定义 dfs(node)：把从 node 开始的这一层（连同所有子层）扁平化，并返回最后一个节点。遍历当前层，遇到有 child 的节点时先递归得到子链表的尾节点 last。把 child 接到当前节点之后，再把 last 接到原来的 next 之前。d 为嵌套层数。

每个节点只访问一次，不需要反复找子链表的尾。递归需要 O(d) 栈空间，嵌套很深时可能栈溢出。

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        def dfs(node):
            # 把以 node 开头的这一层（含所有子层）扁平化，返回最后一个节点
            last = None
            cur = node
            while cur:
                nxt = cur.next
                if cur.child:
                    child_last = dfs(cur.child)
                    cur.next = cur.child
                    cur.child.prev = cur
                    cur.child = None
                    child_last.next = nxt
                    if nxt:
                        nxt.prev = child_last
                    last = child_last
                else:
                    last = cur
                cur = nxt
            return last

        dfs(head)
        return head

class Solution {
    private Node dfs(Node node) {
        Node last = null;
        Node cur = node;
        while (cur != null) {
            Node nxt = cur.next;
            if (cur.child != null) {
                Node childLast = dfs(cur.child);
                cur.next = cur.child;
                cur.child.prev = cur;
                cur.child = null;
                childLast.next = nxt;
                if (nxt != null) nxt.prev = childLast;
                last = childLast;
            } else {
                last = cur;
            }
            cur = nxt;
        }
        return last;
    }

    public Node flatten(Node head) {
        dfs(head);
        return head;
    }
}

class Solution {
public:
    Node* dfs(Node* node) {
        Node* last = nullptr;
        Node* cur = node;
        while (cur) {
            Node* nxt = cur->next;
            if (cur->child) {
                Node* childLast = dfs(cur->child);
                cur->next = cur->child;
                cur->child->prev = cur;
                cur->child = nullptr;
                childLast->next = nxt;
                if (nxt) nxt->prev = childLast;
                last = childLast;
            } else {
                last = cur;
            }
            cur = nxt;
        }
        return last;
    }

    Node* flatten(Node* head) {
        dfs(head);
        return head;
    }
};

func flatten(root *Node) *Node {
	var dfs func(node *Node) *Node
	dfs = func(node *Node) *Node {
		var last *Node
		cur := node
		for cur != nil {
			nxt := cur.Next
			if cur.Child != nil {
				childLast := dfs(cur.Child)
				cur.Next = cur.Child
				cur.Child.Prev = cur
				cur.Child = nil
				childLast.Next = nxt
				if nxt != nil {
					nxt.Prev = childLast
				}
				last = childLast
			} else {
				last = cur
			}
			cur = nxt
		}
		return last
	}
	dfs(root)
	return root
}

var flatten = function(head) {
    const dfs = (node) => {
        let last = null;
        let cur = node;
        while (cur) {
            const nxt = cur.next;
            if (cur.child) {
                const childLast = dfs(cur.child);
                cur.next = cur.child;
                cur.child.prev = cur;
                cur.child = null;
                childLast.next = nxt;
                if (nxt) nxt.prev = childLast;
                last = childLast;
            } else {
                last = cur;
            }
            cur = nxt;
        }
        return last;
    };
    dfs(head);
    return head;
};

function flatten(head: _Node | null): _Node | null {
    const dfs = (node: _Node | null): _Node | null => {
        let last: _Node | null = null;
        let cur = node;
        while (cur) {
            const nxt = cur.next;
            if (cur.child) {
                const childLast = dfs(cur.child) as _Node;
                cur.next = cur.child;
                cur.child.prev = cur;
                cur.child = null;
                childLast.next = nxt;
                if (nxt) nxt.prev = childLast;
                last = childLast;
            } else {
                last = cur;
            }
            cur = nxt;
        }
        return last;
    };
    dfs(head);
    return head;
}

链表专题的其他题目

查看链表全部题目 →