排序鏈表到位

Question

我有一個結構類型的節點：

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

我使用這個節點結構的鏈接列表。我可以排序使用另一個鏈接列表和複製節點值有這個鏈表，但我想實現在鏈表selection sort。我已經經歷了一些問題和文章，但是我不清楚這是否可能。我是否需要一個索引來實現選擇排序？如果可能的話，我該如何繼續？

Answer 1

選擇排序是爲數組，向量的事情，有隨機訪問迭代器和類似next指針沒有鏈接（鏈接交換元素時創建的開銷）。對於一個簡單的列表排序，從一個空列表開始，它將成爲排序列表，比如說這是struct node * sorted = NULL; 。從原始列表中逐個刪除一個節點，並按排序順序將它們插入排序列表（以空列表開頭）。

寫一些代碼，並與您到目前爲止已經試過什麼更新你的答案。