javascript - 在Javascript中有效地对链表进行排序？

Question

在 Javascript/NodeJS 中对链表进行排序的最有效方法是什么？如果我有一个对象数组，其中一个id和comesAfter引用id列表中前一项的，我怎样才能把它按顺序排列？

解决方案中的 ES6 功能很好用。它不应该修改原始数组，而是返回一个新数组。（但是，如果不难展示如何在适当的位置进行操作，那也有助于了解。）

// before sorting
[
  { id: "three", comesAfter: "two" },
  { id: "one", comesAfter: null },
  { id: "four", comesAfter: "three" },
  { id: "two", comesAfter: "one" },
]

// after sorting
[
  { id: "one", comesAfter: null },
  { id: "two", comesAfter: "one" },
  { id: "three", comesAfter: "two" },
  { id: "four", comesAfter: "three" },
]

标签： javascriptecmascript-6linked-list

Answer 1

创建一个对象似乎是合理的，如下所示：

var obj = {};
for (var i = 0; i < input.length; i++) {
    obj[input[i].comesAfter] = input[i];
}

现在，让我们生成输出：

var index = 0;
var output = [obj.null];
while (++index < input.length) {
    output[index] = obj[output[index - 1].id];
}