鏈接列表中高效的「插入」功能

Question

在一次採訪中，我被要求以這樣一種方式爲鏈接列表編寫插入函數，插入後，朝向插入元素頭部的元素應該更大，尾部與插入元素相比應該更小。

我實現了我的代碼如下步驟：

1. 最初以降序排列的鏈表。
2. 獲取元素。
3. 以這種方式插入元素，即使插入後鏈接列表也會以降序排列。

但我被告知我的方式效率不高。

請讓我知道是否有有效的方法來實現相同。

Answer 1

排序是O(n log n)操作。如果你仔細閱讀這個問題，他們從不說清單應該排序，所以不要進行排序操作。你應該做的是從一個只有你的元素的新列表開始，然後對於原始列表中的每個元素，將它附加到前面（如果大於新元素）或否則在後面。