使用下一个和上一个值排序列表

Question

我有一些对象，它们的值是id, next, prev。其中next和prev具有另一个id的值。这些对象的顺序相当随意。我要按以下顺序获取它们：列表中没有上一个对象的对象位于位置1，然后是具有第一个对象的ID的对象的下一个值，依此类推。

• 排序功能应返回列表列表
• 如果列表中存在无法连接的不同部分，则这些部分将位于两个单独的列表中。 （可以这么说：我们有2个结尾和2个开头）
• 0表示没有上一个/下一个
• 排序功能就复杂性而言应尽可能高效
• 伪代码很好，不需要Javascript

let list = [
{"id": 181, "next": 182, "prev": 231},
{"id": 182, "next": 253, "prev": 181},
{"id": 230, "next": 231, "prev": 0},
{"id": 231, "next": 181, "prev": 230},
{"id": 253, "next": 254, "prev": 182},
{"id": 254, "next": 0, "prev": 253},
]

console.log("unordered", list.map(x => x.id))
let falsesorted = sortByNextPrev(list);
falsesorted.forEach(sub => {
  console.log(sub.map(x => x.id));
});

function sortByNextPrev(list){
 var sorted = list.reduce((acc,l) => {
     let last = acc[acc.length-1];
    if(last.length === 0 || last[last.length-1].next === l.id){
        last.push(l)
    }
    else if(last[0].prev === l.id){
        last.unshift(l);
    }
    else{
        acc.push([l]);
    }
    return acc;
},[[]]);
return sorted;
}

我的功能显然无法实现我想要的功能。我尝试实现的顺序是230,231,181,182,253,254。

我试图绕过它，但是还没有找到有效的解决方案。我想我可以构建一个真正愚蠢的功能，但我宁愿不这样做。

Answer 1

只需使用查找函数并从第一个元素开始，然后将它们依次放在结果数组中。查找可以通过循环简单而愚蠢的完成，可以在已排序的数组中进行二进制搜索，也可以通过查找表进行优化。

让我们选择最后一种方法，无论如何我们需要一次迭代才能找到第一个元素：

const byId = new Map();
const firsts = [];
for (const el of list) {
    byId.set(el.id, el);
    if (!el.prev) firsts.push(el);
}
const results = firsts.map(first => {
    const result = [];
    for (let x = first; x != null; x = byId.get(x.next))
        result.push(x);
    return result;
});