多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。
这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。
给定位于列表第一级的头节点,请扁平化列表,即将这样的多级双向链表展平成普通的双向链表,使所有结点出现在单级双链表中。
示例 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]
解释:输入的多级列表如下图所示:
1---2---NULL
|
3---NULL
示例 3:输入:head = [] 输出:[]
如何表示测试用例中的多级链表?
以 示例 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]
提示:节点数目不超过 1000
1 <= Node.val <= 10^5
注意:本题与主站 430 题相同
1、递归;时间复杂度O(n),空间复杂度O(n)
func flatten(root *Node) *Node {
if root == nil {
return nil
}
res := &Node{}
cur := res
for root != nil {
cur.Next = root
root.Prev = cur
cur = cur.Next
root = root.Next
// 处理子节点
if cur.Child != nil {
ch := flatten(cur.Child)
cur.Child = nil
cur.Next = ch
ch.Prev = cur
// 指针移动
for cur.Next != nil {
cur = cur.Next
}
}
}
res.Next.Prev = nil
return res.Next
}
2、递归;时间复杂度O(n),空间复杂度O(n)
var arr []*Node
func flatten(root *Node) *Node {
arr = make([]*Node, 0)
dfs(root)
for i := 0; i < len(arr); i++ {
if i+1 < len(arr) {
arr[i].Next = arr[i+1]
}
if i > 0 {
arr[i].Prev = arr[i-1]
}
arr[i].Child = nil
}
return root
}
func dfs(root *Node) {
if root == nil {
return
}
arr = append(arr, root)
dfs(root.Child)
dfs(root.Next)
}
3、迭代;时间复杂度O(n),空间复杂度O(n)
func flatten(root *Node) *Node {
cur := root
stack := make([]*Node, 0)
for cur != nil {
// 处理child
if cur.Child != nil {
if cur.Next != nil {
stack = append(stack, cur.Next)
}
cur.Child.Prev = cur
cur.Next = cur.Child
cur.Child = nil
continue
}
if cur.Next != nil {
cur.Child = nil
cur = cur.Next
continue
}
if len(stack) == 0 {
break
}
last := stack[len(stack)-1]
stack = stack[:len(stack)-1]
cur.Next = last
last.Prev = cur
cur = last
}
return root
}
Medium题目,题目同leetcode 430.扁平化多级双向链表
页面更新:2024-05-19
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号