1.4 如何對鏈表進行重新排序

【出自WR筆試題】

難度系數(shù)：★★★☆☆

被考察系數(shù)：★★★★☆

題目描述：

給定鏈表L0→L1→L2→…→Ln-1→Ln，把鏈表重新排序為L0→Ln→L1→Ln-1→L2→Ln-2→…。要求：①在原來鏈表的基礎(chǔ)上進行排序，即不能申請新的結(jié)點；②只能修改結(jié)點的next域，不能修改數(shù)據(jù)域。

分析與解答：

主要思路為：

1）首先找到鏈表的中間結(jié)點。

2）對鏈表的后半部分子鏈表進行逆序。

3）把鏈表的前半部分子鏈表與逆序后的后半部分子鏈表進行合并，合并的思路為：分別從兩個鏈表各取一個結(jié)點進行合并。實現(xiàn)方法如下圖所示。

實現(xiàn)代碼如下：

程序的運行結(jié)果為

算法性能分析：

查找鏈表的中間結(jié)點的方法的時間復(fù)雜度為O（N），逆序子鏈表的時間復(fù)雜度也為O（N），合并兩個子鏈表的時間復(fù)雜度也為O（N）。因此，整個方法的時間復(fù)雜度為O（N），其中，N表示鏈表的長度。由于這種方法只用了常數(shù)個額外指針變量，因此，空間復(fù)雜度為O（1）。

引申：如何查找鏈表的中間結(jié)點

分析與解答：

主要思路：用兩個指針從鏈表的第一個結(jié)點開始同時遍歷結(jié)點，一個快指針每次走兩步，另外一個慢指針每次走一步；當快指針先到鏈表尾部時，慢指針則恰好到達鏈表中部（快指針到鏈表尾部時，當鏈表長度為奇數(shù)時，慢指針指向的即是鏈表中間指針，當鏈表長度為偶數(shù)時，慢指針指向的結(jié)點和慢指針指向結(jié)點的下一個結(jié)點都是鏈表的中間結(jié)點）。上面的代碼FindMiddleNode就是用來求鏈表的中間結(jié)點的。