单链表的数据，JS如何排序

Question

单链表的数据，需要根据next重新排序。

[
    {id:3,next:'no'}
    {id:2,next:3}
    {id:1,next:2},
]
根据next重排
输出
[
    {id:1,next:2},
    {id:2,next:3}
    {id:3,next:'no'}
]

Answer 1

let val = [
  { id: 3, next: 'no' },
  { id: 2, next: 3 },
  { id: 1, next: 2 },
];
let obj = {}, res = [];
val.map(item => {
  obj[item.next] = item;
  // 找到末尾
  if (item.next === 'no') {
    res.push(item);
  }
});
while(res.length < val.length) {
  // res中第一个元素的id，也是即将进入res数组的元素的next的值
  let v = res[0].id;
  res.unshift(obj[v]);
}
console.log(res);

Answer 2

const list = [
  { id: 3, next: 'no' },
  { id: 2, next: 3 },
  { id: 1, next: 2 },
]

const map = new Map(list.map(item => [item.id, item]))
const set = new Set(list.map(item => item.next))
// id没有对应的next，则为头节点
const [firstNode] = list.filter(item => !set.has(item.id))

let nextNode = map.get(firstNode.next)
const sortedList = [firstNode]
while (nextNode) {
  sortedList.push(nextNode)
  nextNode = map.get(nextNode.next)
}

console.log(sortedList)

Answer 3

var arr = [
{id:3,next:'no'},
{id:2,next:3},
{id:1,next:2},
].sort((a, b) => {
if(a.next == 'no'){
  return 1;
}
if(b.next == 'no'){
  return -1;
}
return a.next - b.next 
});

https://developer.mozilla.org...