4.4 反轉鏈表

單向鏈表最大的特點就是其單向性，只能順著指向下一個節點的指針方向從頭到尾遍歷鏈表而不能反方向遍歷。這種特性用一句古詩來形容正合適：黃河之水天上來，奔流到海不復回。

有些面試題只有從鏈表尾節點開始遍歷到頭節點才容易解決。這個時候可以先將鏈表反轉，然后在反轉的鏈表中從頭到尾遍歷，這就相當于在原來的鏈表中從尾到頭遍歷。

下面介紹如何反轉鏈表，以及如何利用反轉鏈表來解決典型的算法面試題。

面試題24：反轉鏈表

分析：首先確定函數的返回值。需要返回的是反轉后鏈表的頭節點。顯然，反轉之后鏈表的頭節點是原始鏈表的尾節點，也就是說，原始鏈表中的next指針指向null的節點。

然后借助圖形直觀地分析如何通過調整鏈表中指針的方向來正確地反轉鏈表。在如圖4.9（a）所示的鏈表中，i、j和k是3個相鄰的節點。假設經過若干次反轉操作已經把節點i之前的指針都反轉了，這些節點的next指針都指向前面一個節點。接下來把節點j的next指針指向節點i，此時的鏈表結構如圖4.9（b）所示。

由于節點j的next指針指向了它的前一個節點i，因此鏈表在節點j和k之間斷開，無法在鏈表中遍歷到節點k。為了避免鏈表斷開，需要在調整節點j的next指針之前把節點k保存下來。

也就是說，在調整節點j的next指針時，除了需要知道節點j本身，還需要知道節點j的前一個節點i，這是因為需要把節點j的next指針指向節點i。同時，還需要事先保存節點j的下一個節點k，以防止鏈表斷開。因此，在遍歷鏈表逐個反轉每個節點的next指針時需要用到3個指針，分別指向當前遍歷到的節點、它的前一個節點及后一個節點。

有了前面的分析，就可以編寫出如下所示的代碼來反轉鏈表：

在上述代碼中，變量cur指向當前遍歷到的節點，變量prev指向當前節點的前一個節點，而變量next指向下一個節點。每遍歷一個節點之后，都讓變量prev指向該節點。在遍歷到尾節點之后，變量prev最后一次被更新，因此，變量prev最終指向原始鏈表的尾節點，也就是反轉鏈表的頭節點。

顯然，上述代碼的時間復雜度是O（n），空間復雜度是O（1）。

面試題25：鏈表中的數字相加

分析：這是一個看起來很簡單的題目。很多應聘者的第一反應是根據鏈表求出整數，然后直接將兩個整數相加，最后把結果用鏈表表示。這種思路的最大的問題是沒有考慮到整數有可能會溢出。當鏈表較長時，表示的整數很大，可能會超出int甚至long的范圍，如果根據鏈表求出整數就有可能會溢出。

由于示例中給出的兩個鏈表的長度是一樣的，因此很多應聘者沒有經過細致思考就以為只要從兩個鏈表的頭節點開始逐個數位相加就可以。

其實，只要分析一個長度不相同的兩個鏈表相加的例子就能發現題目沒有這么簡單。例如，兩個分別表示整數984和18的鏈表，它們相加時應該是984中的十位數8和18中的十位數1相加，984的個位數4和18的個位數8相加。此時不能從兩個鏈表的頭節點開始相加，而是應該把它們的尾節點對齊并把對應的數位相加。

通常，兩個整數相加都是先加個位數，再加十位數，然后依次相加更高位數字。由于題目中的整數使用單向鏈表表示，因此先將兩個尾節點相加，再將兩個整數的倒數第2個節點相加，并依次對前面的節點相加。

但是兩個尾節點相加之后，在單向鏈表中就無法前進到倒數第2個節點。在單向鏈表中只能從前面的節點朝著next指針方向前進到后面的節點，卻無法從后面的節點前進到前面的節點。

解決這個問題的辦法是把表示整數的鏈表反轉。反轉之后的鏈表的頭節點表示個位數，尾節點表示最高位數。此時從兩個鏈表的頭節點開始相加，就相當于從整數的個位數開始相加。

在做加法時還需要注意的是進位。如果兩個整數的個位數相加的和超過10，就會往十位數產生一個進位。在下一步做十位數相加時就要把這個進位考慮進去。

圖4.11總結了用鏈表表示的兩個整數984和18相加的過程。先把兩個表示整數的鏈表反轉，再在兩個反轉之后的鏈表中逐個節點實現加法，最后把表示和的鏈表反轉。

該思路對應的代碼如下所示：

函數reverseList和面試題24中的函數reverseList完全一樣，這里就不再重復介紹。

面試題26：重排鏈表

分析：如果仔細觀察輸入鏈表和輸出鏈表之間的聯系，就能發現重排鏈表其實包含以下幾個操作。首先把鏈表分成前后兩半。在示例鏈表中，前半段鏈表包含1、2、3這3個節點，后半段鏈表包含4、5、6這3個節點。然后把后半段鏈表反轉。示例鏈表的后半段鏈表反轉之后，節點的順序變成6、5、4。最后從前半段鏈表和后半段鏈表的頭節點開始，逐個把它們的節點連接起來形成一個新的鏈表。先把前半段鏈表和后半段鏈表的頭節點1和6連接起來，再把處在第2個位置的節點2和5連接起來，最后把兩個尾節點3和4連接起來，因此在新的鏈表中節點的順序是1、6、2、5、3、4。

需要首先解決的問題是如何把一個鏈表分成兩半。如果能夠找到鏈表的中間節點，那么就能根據中間節點把鏈表分割成前后兩半。位于中間節點之前的是鏈表的前半段，位于中間節點之后的是鏈表的后半段。

可以使用雙節點來尋找鏈表的中間節點。如果一快一慢兩個指針同時從鏈表的頭節點出發，快的指針一次順著next指針向前走兩步，而慢的指針一次只走一步，那么當快的指針走到鏈表的尾節點時慢的指針剛好走到鏈表的中間節點。

一個值得注意的問題是，鏈表的節點總數既可能是奇數也可能是偶數。當鏈表的節點總數是奇數時，就要確保鏈表的前半段比后半段多一個節點。

在上述代碼中，變量fast表示走得快的指針，一次走兩步，變量slow表示走得慢的指針，一次只走一步。當變量fast指向尾節點時，變量slow指向前半段的最后一個節點。

變量slow指向的節點的下一個節點就是后半段的頭節點，用變量temp表示。然后調用函數reverseList反轉鏈表的后半段。該函數和前面幾道面試題中的函數reverseList完全一樣，這里就不再重復介紹。

面試題27：回文鏈表

分析：如果不考慮輔助空間的限制，直觀的解法是創建一個新的鏈表，鏈表中節點的順序和輸入鏈表的節點順序正好相反。如果新的鏈表和輸入鏈表是相同的，那么輸入鏈表就是一個回文鏈表。只是這種解法需要創建一個和輸入鏈表長度相等的鏈表，因此需要O（n）的輔助空間。

仔細分析回文鏈表的特點以便找出更好的解法。回文鏈表的一個特性是對稱性，也就是說，如果把鏈表分為前后兩半，那么前半段鏈表反轉之后與后半段鏈表是相同的。在如圖4.13所示的包含6個節點的鏈表中，前半段鏈表的3個節點反轉之后分別是3、2、1，后半段鏈表的3個節點也分別是3、2、1，因此它是一個回文鏈表。

如圖4.13所示，鏈表的節點總數是偶數。如果鏈表的節點總數是奇數，那么把鏈表分成前后兩半時不用包括中間節點。例如，一個鏈表中的節點順序是1、2、k、2、1，前面兩個節點反轉之后是2、1，后面兩個節點也是2、1，不管中間節點的值是什么該鏈表都是回文鏈表。

通過如此分析可知，這個題目的解法和面試題26的解法基本類似，都是嘗試把鏈表分成前后兩半，然后把其中一半反轉。基于這種思路可以編寫出如下所示的代碼：

上述代碼仍然是用一快一慢兩個指針找出鏈表中的中間節點，并以此把鏈表分成前后兩半。不管鏈表的節點總數是奇數還是偶數，變量slow都指向鏈表前半段的最后一個節點，變量secondHalf都指向鏈表后半段的第1個節點。如果鏈表的前半段反轉之后和鏈表的后半段相同，那么它就是一個回文鏈表。

函數reverseList用來反轉一個鏈表，由于該函數和前面幾道面試題中的函數reverseList完全一樣，因此這里就不再重復介紹。

通過解決這幾道典型的面試題可以發現，反轉鏈表是面試中經常出現的操作，所以能熟練、正確地編寫出反轉鏈表的代碼非常重要。