3.2　回文鏈表

鏈表相對于字符串來說難度會增加一點，但其實二者都屬于線性數據結構，因此難度也只表現在寫法上，在思路上并沒有增加太大的難度。

題目描述（第234題）

請判斷一個鏈表是否為回文鏈表。

示例1

輸入：1→2

輸出：False

示例2

輸入：1→2→2→1

輸出：True

進階

你能否用O(n)時間復雜度和O(1)空間復雜度解決此題？

思路

這是一道Amazon的面試題，難度級別為簡單，是一道熱身題。鏈表不同于數組（字符串本質上是字符數組），不支持隨機訪問。對于單鏈表來說，只有一個指向下一個節點的指針。如果不考慮復雜度，可以將鏈表進行一次遍歷，遍歷的同時將值放到一個數組中，然后可以采用字符串的思路去解決。這種算法需要額外的數組存儲鏈表的值，因此這種算法的空間復雜度是O(n)。空間上可以進一步優化。下面介紹一種空間復雜度為O(1)的解法。

首先使用快/慢指針的技巧找到中點，找到中點的同時將前半部分鏈表進行反轉。然后將慢指針和慢指針的前一個指針同時移動，如果兩者指向的數字有一個不同則說明不是回文，否則則是回文。這里有兩個要點。

●　如何找到中點？我們只需要建立快/慢指針，快指針fast每次走兩步，慢指針slow每次走一步。這樣當快指針走到終點時，慢指針剛好走到中間位置。

●　如何進行反轉？其實鏈表反轉是一個單獨且常見的考點，力扣（LeetCode）上也有原題（第206題反轉鏈表，見參考鏈接/正文[8]）。我們使用一個變量記錄前驅pre，一個變量記錄后繼next，不斷更新current.next=pre就好了。

反轉鏈表的代碼如下所示。

找到中點時鏈表情況如下圖所示。

之后pre和slow分別向前、向后遍歷即可。當然這里的“向前”本質上還是借助于next指針移動，只不過我們已經對前半部分進行了反轉，因此可以通過next找到前驅節點。

代碼

復雜度分析

●　時間復雜度：算法由兩部分組成。第1部分是找到中點，這部分的時間復雜度為O(n)；第2部分是從中點分別向左和向右移動，這部分的時間復雜度同樣是O(n)，因此總的時間復雜度為O(n)，其中n為節點數。

●　空間復雜度：O(1)。