展平多级双向链表
# 📃 题目描述
题目链接:
- 剑指 Offer II 028. 展平多级双向链表 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 430. 扁平化多级双向链表 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。
给定位于列表第一级的头节点,请扁平化列表,即将这样的多级双向链表展平成普通的双向链表,使所有结点出现在单级双链表中。
示例 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 为例:
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]
# 🔔 解题思路
理解题目很重要
其实很简单
比如有 a —> b 这样两个节点,然后 a 还有一个 child 指针,指向一个新的链表,题目就是要把这个 child 链表插入到 a 和 b 之间。
所以,对于这个插入操作,我们需要四个关键信息:
- a 节点
- a 的 next 节点:b
- a 的 child 链表的头节点
- a 的 child 链表的尾节点
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution {
public Node flatten(Node head) {
dfs(head);
return head;
}
// dfs 展平以 head 为头节点的链表之后返回链表的尾节点
public Node dfs(Node head) {
Node node = head;
Node tail = null;
while (node != null) {
// 记录 node 后继节点
Node next = node.next;
if (node.child != null) {
Node child = node.child;
// 递归调用展平 child,返回尾节点
Node childTail = dfs(child);
// 删除 child 指针
node.child = null;
// 将 child 链表插入 node 和 node.next 之间
node.next = child;
child.prev = node;
childTail.next = next;
if (next != null) {
next.prev = childTail;
}
tail = childTail;
}
// 如果 node 没有 child,那么无须展平
else {
tail = node;
}
node = next;
}
return tail;
}
}
在上述代码中,递归函数 flattenGetTail 在展平以head为头节点的链表之后返回链表的尾节点。在该函数中需要逐一扫描链表中的节点。如果一个节点node有子链表,由于子链表也可能有嵌套的子链表,因此先递归调用 flattenGetTail 函数展平子链表,子链表展平之后的头节点是child,尾节点是childTail。
最后将展平的子链表插入节点node和它的下一个节点next之间,即把展平的子链表的头节点child插入节点node之后,并将尾节点childTail插入节点next之前。
# 💥 复杂度分析
- 空间复杂度:函数 flattenGetTail 的递归调用次数取决于链表嵌套的层数,因此,如果链表的层数为 k,那么该节点的空间复杂度是 O(K)
- 时间复杂度:法每个节点都会遍历一次,如果链表总共有 n 个节点,那么时间复杂度是 O(n)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~