就地排序链表

Question

我有一个结构类型节点：

struct node
{
    int data;
    node *next;
};

我有一个使用这个节点结构的链表。我可以使用另一个链表对这个链表进行排序并在那里复制节点值，但我想在链表中实现一个 selection sort 。我已经浏览了一些问题和文章，但我不清楚这是否可行。我需要一个索引来实现选择排序吗？如果可以，我该如何进行？

Answer 1

选择排序适用于数组、向量、具有随机访问迭代器且没有链接（如 next 指针）的事物（交换元素时链接会产生开销）。对于简单的列表排序，从一个将成为排序列表的空列表开始，假设这是 struct node *sorted = NULL; .一次从原始列表中删除一个节点，然后按排序顺序将它们插入排序列表（以空列表开始）。

编写一些代码并根据您目前尝试过的内容更新您的答案。