c - 在C中对单链表中的元素进行排序

Question

如何对单链表中的元素进行排序（通过一些值，如 list->id）？我想出的想法是找到最大值并保存它的索引。然后遍历列表，使 *head 指针指向该元素...然后将该元素与第一个元素交换。最后一句话……我该怎么办？

Answer 1

交换数据通常更容易，而不是“重新链接”列表，以便更改实际列表节点的顺序。

如果您的字段是整数，您可以执行以下操作：

static void swap_ids(ListNode *a, ListNode *b)
{
  const int a_id = a->id;

  a->id = b->id;
  b->id = a_id;
}

Answer 2

我想说如何对列表进行排序的最佳方法是实现合并排序。

您尝试做的仍然被称为选择排序并且是可行的（实际上它不是很难）。您需要保留一个指向列表中最小元素的指针，然后移动链接，以便将其放置在头元素之前（记住也要移动头）。我是说你需要选择最小元素，因为通常你只在一个链表中保留一个指向 head 的指针。