我正在尝试解决leetcode上的Flatten a Multilevel Doubly Linked List问题。我可以从数组创建一个单链表，但不知道如何创建一个双链表。
您将获得一个双链接列表，其中包含具有下一个指针、上一个指针和额外子指针的节点。此子指针可能指向也可能不指向单独的双链接列表，该列表也包含这些特殊节点。这些子列表可能有自己的一个或多个子列表，依此类推，以生成多级数据结构，如下例所示。
给定列表第一级的头，展平列表，使所有节点显示在一个单级双链接列表中。让curr是一个具有子列表的节点。子列表中的节点应出现在展开列表中的curr之后和curr.next之前。
返回扁平列表的头部。列表中的节点必须将其所有子指针设置为null。
Ques链接：压扁多级双链接列表
我的代码：
/**
* // 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) {
let array=[];
let list=head;
const childAdd=(node)=>{
while(node){
array.push(node.val);
if(node.child)
childAdd(node.child);
node=node.next;
}
}
while(list){
array.push(list.val);
if(list.child)
childAdd(list.child);
list=list.next;
}
console.log(array)
let resultList=null
for(let i=array.length-1; i>=0; i--){
resultList={
val:array[i],
next:resultList,
}
let prev=null;
while(head){
delete head.child
resultList.prev=prev;
prev=head;
head=head.next;
}
console.log(resultList)
return resultList;
};
输出：
[
1, 2, 3, 7, 8,
11, 12, 9, 10, 4,
5, 6
]
{
val: 1,
next: { val: 2, next: { val: 3, next: [Object] } },
prev: <ref *1> {
val: 5,
prev: { val: 4, prev: [Object], next: [Circular *1] },
next: { val: 6, prev: [Circular *1], next: null }
}
}
预期输出：
The linked list [1,2,3,7,8,11,12,9,10,4,5,6] is not a valid doubly linked list.
Expected: [1,2,3,7,8,11,12,9,10,4,5,6]
如何添加指向列表resultList中列表上一个节点的prev？
附言：我不想解决这个问题，相反，我想知道如何从数组中创建一个双链表。
LeetCode希望您返回一个Node实例，即一个具有四个属性(还包括child(的对象。
当设置next时，可以正确设置prev属性：下一个节点的prev属性应该成为您设置next属性的对象的反向引用。
因此，请替换这段代码(缺少大括号(：
for(let i=array.length-1; i>=0; i--){
resultList={
val:array[i],
next:resultList,
}
let prev=null;
while(head){
delete head.child
resultList.prev=prev;
prev=head;
head=head.next;
}
有了这个：
for (let i = array.length - 1; i >= 0; i--) {
resultList = new Node(array[i], null, resultList, null);
if (resultList.next) resultList.next.prev = resultList;
}
其他备注
这个解决方案可以通过测试，但效率不是很高。它使用O(n(额外空间，而这可以用O(1(额外空间来完成：
- 避免创建数组
- 避免创建新的
Node实例--重用已有的实例
最困难的部分是从arr创建列表。基本上，我们迭代数组创建节点，将节点连接到前一个，并将前一个连接到节点。这里的技巧是，当遇到null时，将指针(bol(设置为当前列表的开头，然后在遇到null时，我们递增bol。最后，当我们找到一个值时，我们知道要创建一个bol的子节点。
为了完整起见，我添加了解决方案(这是简单的部分(，但可以自己找到。
function Node(val, prev, next, child) {
this.val = val;
this.prev = prev;
this.next = next;
this.child = child;
};
function create_list(arr) {
var prev = null;
var first = null;
var bol = null;
var result = null;
while (arr.length) {
var val = arr.shift();
if (val === null) {
if (bol) {
bol = bol.next;
} else {
bol = first;
prev = null;
}
} else {
var node = new Node(val, prev, null, null);
if (!result) {
result = node;
}
if (bol) {
bol.child = node;
bol = null;
}
if (node.prev) {
node.prev.next = node;
} else {
first = node;
}
prev = node;
}
}
return result;
}
var head = [1, 2, 3, 4, 5, 6, null, null, null, 7, 8, 9, 10, null, null, 11, 12];
var copy = [...head];
var list = create_list(head);
function flatten(list) {
var arr = [];
while (list) {
arr.push(list.val);
if (list.child) {
var brr = flatten(list.child);
arr = arr.concat(brr);
}
list = list.next;
}
return arr;
}
console.log("list as array: " + JSON.stringify(copy))
console.log("flattened list: " + JSON.stringify(flatten(list)))
console.log("example 2: " + JSON.stringify(flatten(create_list([1,2,null,3]))))
console.log("example 3: " + JSON.stringify(flatten(create_list([])))).as-console-wrapper {
max-height: 100% !important;
}function arrayToDoublyLinkedList(array) {
let curr;
let next = null;
let prev = null;
// go backwards so we end up with curr being the head
for(let i = array.length - 1; i >= 0; --i) {
curr = {
val: array[i],
prev: null, // except for the head, will set to a node on the next iteration
next: next,
child: null, // required to be null by the leetcode problem statement
};
if (null !== next) {
next.prev = curr;
}
next = curr;
}
return curr;
}
console.log(arrayToDoublyLinkedList([1,2,3,4,5,6,7,8]));一个相当短的版本：
function llist(arr){
function reduce(acc, val){
return val ? (val.prev = acc, reduce(val, val.next)) : acc;
}
return reduce(null, arr.reduceRight((next, value) => ({value, next}), null));
}
var arr = [1, 2, 3, 4 ,5];
console.log(llist(arr));