Open Tcdian opened 3 years ago
/**
* // 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) {
if (head === null) {
return null;
}
return flattenChild(head)[0];
function flattenChild(head) {
let patrol = head;
let tail = null;
while(patrol !== null) {
tail = patrol;
const next = patrol.next;
if (patrol.child !== null) {
const [childHead, childTail] = flattenChild(patrol.child);
patrol.child = null;
patrol.next = childHead;
childHead.prev = patrol;
childTail.next = next;
if (next !== null) {
next.prev = childTail;
}
tail = childTail;
}
patrol = next;
}
return [head, tail];
}
};
430. Flatten a Multilevel Doubly Linked List
多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。
给你位于列表第一级的头节点,请你扁平化列表,使所有结点出现在单级双链表中。
Example 1
输入的多级列表如下图所示:
扁平化后的链表如下图:
Example 2
Example 3
如何表示测试用例中的多级链表?
以 示例 1 为例:
序列化其中的每一级之后:
为了将每一级都序列化到一起,我们需要每一级中添加值为 null 的元素,以表示没有节点连接到上一级的上级节点:
合并所有序列化结果,并去除末尾的 null:
Note
1 <= Node.val <= 10^5