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 要素の前に配置する必要があります (head も移動することを忘れないでください)。通常、単一のリンクされたリストの先頭へのポインターのみを保持するため、最小限の要素を選択する必要があると言っています。