使用next和prev值對列表進行排序

Question

我擁有值爲id, next, prev的對象。其中next和prev的值爲其他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; 
});