對單鏈表中的元素進行排序C

Question

如何對單鏈表中的元素進行排序（通過某些值，如list-> id）？我想出的想法是找到最大的價值並保存其索引。然後遍歷列表，以便*頭指針指向該元素...然後將該元素與第一個元素交換。最後一句......我該怎麼做？

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

我要說如何排序列表中的最好的辦法是實行merge sort。

你仍然試圖做的是被稱爲選擇排序，是可行的（實際上它不是很難）。您需要將指針保留爲列表中的最小的元素，然後移動鏈接以使其位於head元素之前（請記住也要移動head）。我說你需要選擇最小的元素，因爲通常你只保留一個指向頭的鏈接在一個鏈表中。