题目
你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。
给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。
返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 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]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：
示例 2：
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：输入的多级列表如上图所示。
扁平化后的链表如下图：
示例 3：
输入：head = []
输出：[]
说明：输入中可能存在空列表。
提示：
- 节点数目不超过
1000 1 <= Node.val <= 105
如何表示测试用例中的多级链表？
以 示例 1 为例：
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
序列化其中的每一级之后：
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
合并所有序列化结果，并去除末尾的 null 。
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
解题
方法一：DFS 递归
思路
新建一个 curr 节点复制为头节点的引用，遍历主链表中的每个节点：
- 记录
curr当前的后继节点(next) - 如果当前节点有子链表
- 递归地扁平化子链表，拿到子链表的头节点(
childHead) - 把当前节点的后继结点置为子链表的头节点
- 把子链表的头节点的前驱结点置为当前节点
- 把当前节点的子链表置为空
- 迭代找到子链表的尾节点 (可以从
childHead开始找，也可以从curr开始找，因为curr的后继结点已经被置为childHead) - 把子链表的尾节点的后继结点置为原后继结点(
next) - 如果当前节点不是尾节点的话 (还有后继结点)，把原后继结点的前驱节点置为子链表的尾节点
- 递归地扁平化子链表，拿到子链表的头节点(
- 把当前节点置为之前记下的原后继结点(
next)
最后返回头节点即可。
代码
class Solution {
public Node flatten(Node head) {
Node curr = head;
while (curr != null) {
Node next = curr.next;
if (curr.child != null) {
Node childHead = flatten(curr.child);
curr.next = childHead;
childHead.prev = curr;
curr.child = null;
Node childTail = childHead;
while (childTail.next != null) childTail = childTail.next;
childTail.next = next;
if (next != null) next.prev = childTail;
}
curr = next;
}
return head;
}
}
优化: 处理子链表时同时返回头尾节点
在上面可以发现，递归扁平化子链表时迭代到了子链表的尾节点(childTail)，但在后面链接 next 与 childTail 时又迭代找了一次 childTail，浪费了时间，所以可以用一个新方法 flattenDFS 返回值是扁平化链表头尾节点组成的数组(headAndTail)。
class Solution {
public Node flatten(Node head) {
flattenDFS(head);
return head;
}
private Node[] flattenDFS(Node head) {
Node curr = head, tail = curr;
while (curr != null) {
Node next = curr.next;
if (curr.child != null) {
Node[] childHeadAndTail = flattenDFS(curr.child);
Node childHead = childHeadAndTail[0], childTail = childHeadAndTail[1];
curr.next = childHead;
childHead.prev = curr;
curr.child = null;
curr = childTail;
curr.next = next;
if (next != null) next.prev = curr;
}
if (next == null) tail = curr;
curr = next;
}
return new Node[]{head, tail};
}
}
优化: 处理子链表时返回尾节点
子链表的头节点可以不用返回，直接通过 curr.child 就可以拿到，上面同时返回头尾节点浪费空间，所以新方法 flattenDFS 只返回扁平化链表的尾节点即可。
class Solution {
public Node flatten(Node head) {
flattenDFS(head);
return head;
}
private Node flattenDFS(Node head) {
Node curr = head, tail = curr;
while (curr != null) {
Node next = curr.next;
if (curr.child != null) {
Node childTail = flattenDFS(curr.child);
curr.next = curr.child;
curr.child.prev = curr;
curr.child = null;
curr = childTail;
curr.next = next;
if (next != null) next.prev = curr;
}
if (next == null) tail = curr;
curr = next;
}
return tail;
}
}
方法二：迭代
思路
与递归的思路基本一致，但是每次只能处理一层子链表，所以不能跳过被处理过拼接后的子链表，应该接着子链表继续向后遍历
代码
class Solution {
public Node flatten(Node head) {
// 如果当前 curr 有子链表, 处理完后 curr.next 会变成子链表的头节点
// 也就是不会跳过处理后的子链表, 而是接下去遍历
for (Node curr = head; curr != null; curr = curr.next) {
Node next = curr.next;
if (curr.child != null) {
curr.next = curr.child;
curr.child.prev = curr;
curr.child = null;
Node tail = curr;
while (tail.next != null) tail = tail.next;
tail.next = next;
if (next != null) next.prev = tail;
}
}
return head;
}
}
评论区