3/7 演算法題詳解：Reverse a Singly Sublist 反轉一個子單向鏈表

本視頻來自於北美CS刷題神器BitTiger Pro。

單向鏈表真是一個有趣的東西，我們總是可以從單向鏈表方面找到一些有意思的問題，今天的問題就是單向鏈表節點間順序調整問題的擴展。

下面是我們今天提出的問題的具體說明：給出一個單向鏈表L以及兩個整數s和f，將鏈表L的第s個節點為頭，以第f個節點為尾的子鏈表進行順序的反轉。其中鏈表L的節點從編號1開始的，比如頭節點就是第一個節點。還有一個要求就是在實現過程中盡量不去申請額外的空間，這就意味著我們需要使用一些原地演算法（in-place）的思路。

比如說我們給出如下圖的鏈表L，並且s=2，f=5，那麼返回的鏈表就需要像下圖所示的鏈表一樣。

由於給出的s=2，f=5，所以我們需要反轉的子鏈表是從第2個節點到第5個節點，我們需要將這個子鏈表進行翻轉，即將7-2-4-18的順序變為18-4-2-7的順序，並且不去變更鏈表的其他部分的順序，然後返回一個新的鏈表。

也許你腦海中會立即浮現出一個想法就是我們先遍歷整個鏈表，找到需要反轉的子鏈表作為分隔鏈表，然後將這個子鏈表賦給一個新的鏈表後進行反轉，最後把轉換後的鏈表替換回原始的鏈表中。當然這是一種可行的方法，但是通過分析時間複雜度我們發現需要遍歷鏈表兩次，時間複雜度約是O(2n)，而從空間複雜度來說如果鏈表L很長，f遠大於s，就可能導致新申請的鏈表會很長，需要申請大量空間，那能只訪問鏈表一遍並用最少的空間就實現這個功能嗎？答案是肯定的。

接下來我們來說明一下我們提出的第二種優化後的方法。

Step 0:預處理

在處理過程中會出現一種特殊情況就是當s=1的時候，整個鏈表在反轉後的頭節點是會變的，然後去找新的鏈表的頭節點就很難。為了避免這種情況發生，以便我們在返回鏈表的時候能夠有一個確定的鏈表頭節點，需要定義一個dummyHead（空頭）節點來作為鏈表的頭節點。定義一個curr指針來指向當前所在節點，將 dummyHead節點作為初始值賦給curr指針。如下圖所示：

Step 1：遍歷到s-1節點上

在這個步驟中，由於s值的給出，指示了子鏈表的頭節點位置，所以需要將curr指針指向第s-1個節點上（單向鏈表中已知上一節點找下一節點很好找，但反向尋找卻不易）。

在本例中s=2，所以我們需要將curr指針移到值為7的節點的前一個節點，即值為6的節點位置，如下圖所示：

Step 2：為交換（swap）做準備

在這步中我們定義一個prev節點，把curr節點賦給prev，把curr節點移到下一個節點。如下圖所示：

Step 3：（循環第一次）開始交換第一個節點

這裡需要注意，交換數組中兩個元素的位置很容易，但是在鏈表中要相當小心，一旦處理不得當，我們的鏈表將會斷裂或者出現循環。首先定義一個temp節點，指向curr節點的next節點，然後把temp的next節點賦給curr的next節點，再把prev的next節點賦給temp的next節點，最後把temp賦給prev的next節點。將順序從6-7-2-4-18變為6-2-7-4-18，交換了2和7的位置。參與交換的有三個節點，prev，curr，temp，每次循環執行的重點就是把temp節點，也就是最後面的那個節點交換到最前面來。稍微有點繞，可以藉助下圖幫助理解：

Step 4：（循環第二次）開始交換第二個節點

同上一步操作，順序從6-2-7-4-18變為6-4-2-7-18，過程如下圖所示：

以此類推，一直反轉到第f個節點。

Step 5：返回結果

將子鏈表反轉完成後，直接將dummyHead的下一個節點作為返回值，而不用考慮反轉完成後新的鏈表的頭節點是哪個節點。

完整實現代碼如下：

本視頻來自於北美CS刷題神器BitTiger Pro。

每月更新的BitTiger Pro是一個覆蓋了CS和數據科學方向最新高頻面試題的精講視頻庫。訂閱後，你可以在Code Evaluation System親自練習這道題。