使用mergesort列表

Question

Mergesort可以在列表中就地完成;與數組不同。
但是，我還沒有找到一個參考，它解釋了這是如何實現的。
任何指針表示讚賞。

Answer 1

它實際上是可能的，雖然不是直接的，實現了陣列就地歸併排序。通過鏈接列表，問題變得非常簡單。鏈表中的每個節點只有一個值和一個指向下一個節點的指針。把鏈表分成兩半是很簡單的。只需遍歷中間節點，將其後繼者作爲第二個列表的頭部，然後將後繼者設置爲null。

合併步工作就像你所期望的。不要創建任何新節點，只需重新鏈接兩個列表中的節點即可。