連結串列反轉與雙向連結串列就是這麼簡單
一、最後
上一篇文章《 面試中必問的幾道連結串列問題 》給你們講解了幾道連結串列相關的面試題。
其實，我不認為那些是好的面試題。
畢竟快慢指標的方法屬於啟發式演算法，不是誰都能想到的。
並且那些題與連結串列的關係不太大。
連結串列的重點應該在於指標的操作。
比如我在上篇文章最後，問大家都遇到連結串列的什麼問題。
有一個人回覆說：連結串列實現快速排序。
連結串列實現快排也很簡單，不過這篇文章暫時不講解，大家可以先思考一下。
這篇文章我們就來體驗一些操作連結串列的樂趣吧
二、反轉連結串列
題意：給一個連結串列，求反轉後的連結串列。
思路：遍歷連結串列，每次刪除一個節點，然後插入到最前面即可。
三、移除連結串列元素
題意：給一個連結串列，求刪除指定值後的連結串列。
思路：遍歷連結串列，判斷是否等於指定值，等於則刪除。
注意實現：由於刪除節點的時候，上一個節點需要執行下一個節點，所以我們需要儲存上一個節點的指標。
四、奇偶連結串列
題意：給一個連結串列，求按奇偶位置將連結串列分為兩部分，奇數的在前面，偶數的在後面。
思路：這個使用 雙指標 思路很容易處理。
前面的指標指向已處理好的奇數部分的最後，後面的指標正常遍歷連結串列。
當後面指標是奇數位置時，將對應的節點刪除，插入到前面的之後後面，然後維護兩個指標的偏移量即可。
五、迴文連結串列
題意：給一個連結串列，求判斷這個連結串列是不是迴文連結串列。
要求：使用 O(n) 的時間複雜度， O(1) 的空間複雜度。
思路：這裡解釋一下要求的含義。
O(n) 的時間複雜度並不是說只能迴圈 n 次，而是要接近 n 次。甚至迴圈 2n 次也是可以的。
O(1) 的空間複雜度並不是說只能定義一個變數，而是不能定義 n 個空間，定義幾個變數都是沒問題的。
回到這道題。
迴文的意思指的是，一個串正著看和倒著看完全一樣。
對於陣列，一般從首尾兩頭逐漸向中間移動，遍歷一半就可以判斷出是否是迴文。
連結串列的難點在於只能從前到後，不能從後到前。
所以這裡我們需要想辦法來從後到前遍歷其中一半的連結串列。
簡單思考一下，你是不是想到了對後半段連結串列進行反轉呢？
換句話說就是將一個連結串列拆分為兩個連結串列，然後反轉其中一個，他們對比應該是一樣的（假設兩個長度一樣）。
由於連結串列有可能是奇數長度，這樣其中一個的長度比另一個大一。
此時你只需要反轉後面那個連結串列，忽略長連結串列最後一個元素即可。
六、雙向連結串列
題意：自己實現一個雙向連結串列。
思路：雙向連結串列，顧名思義，不僅像單向連結串列那樣有一個向後的 next 指標，還有一個向前的 prev 指標。
這時候，連結串列插入或刪除一個節點的時候，不僅需要維護 next 指標，還需要維護 prev 指標。
插入一個節點 cur 的時候， cur 需要先指向上一個節點和下一個節點。
然後上一個節點的 next 和 下一個節點的 prev 都指向當前節點。
刪除一個節點的時候，簡單一下。
上一個節點直接指向 cur 的下一個節點，而 cur 的下一個節點指向 cur 的上一個節點即可。
當然，這兩個操作有一個注意實現。
那就是操作連結串列頭和連結串列尾的時候，需要先判斷上一個節點和下一個節點是否存在。
不存在就不需要操作了。
七、最後
好了，這裡給你們介紹一些簡單的連結串列演算法，如反轉連結串列，刪除指定值。也給你們介紹了雙向連結串列。
到目前為止，這些都是比較簡單的操作，下面文章我們來看看連結串列的高階操作吧。
-EOF-