Appearance
430. 扁平化多级双向链表
题目描述
你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。
给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。
返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。
示例 1：
1000
序列化其中的每一级之后：
[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]
难度： Medium
题解代码
javascript
/**
* // Definition for a Node.
* function Node(val,prev,next,child) {
* this.val = val;
* this.prev = prev;
* this.next = next;
* this.child = child;
* };
*/
/**
* @param {Node} head
* @return {Node}
*/
var flatten = function(head) {
dfs(head)
return head
};
function dfs (head) {
let cur = head, last = null
while (cur) {
if (cur.child) {
const next = cur.next
const childLast = dfs(cur.child)
cur.next = cur.child
cur.child.prev = cur
if (next) {
childLast.next = next
next.prev = childLast
}
cur.child = null
last = childLast
} else {
last = cur
}
cur = cur.next
}
return last
}