這是一個簡單的鍊表操作問題，在leetcode上面有52.7%的通過率，難度是簡單。但是還是想在這裡基於python做一下總結，順便總結一下鍊表的各種操作。
首先先看一下leetcode上面的題目：
反轉一個單鍊表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞歸地反轉鍊表。你能否用兩種方法解決這道題？
看完了題目，很直白，就是轉過來。我們嘗試對這道題進行解決。這道題用python至少會有三種解決方案。
首先是鍊表的數據結構定義：
1.將鍊表遍歷進list中，然後利用切片反轉list，再將list填充到鍊表中即可。這是最簡單的一種思考邏輯，但是也比較消耗性能。時間和空間複雜度都為O(n)。
2.另一種迭代算法，是一種純粹交換的迭代，筆者這裡截取了leetcode速度最快的一種。
這一波交換操作，我們可以畫個示意圖就知道他的交換是一種怎麼樣的交換。
從圖中可以看出，循環的作用就是將反向指針進行保存。同時令將指針轉向的功能。
3.最後一種方案是採用遞歸的方式進行鍊表反轉。這種方式也需要一定的理解。我們先展示一下代碼。
這種解法其實理解起來只有兩部分內容，傳遞反向指針和進行指針反向拼接。我們先來理解一下指針反向拼接這個操作。
如此循環即可將鍊表反轉過來。但是還有個關鍵就是將最後一個指針傳遞出來。我們可以看到之前的代碼中，end傳出來後是一直沒有做任何操作的。不停的return出最後一個指針。所以就將最後一個指針傳遞了出來。
以上就是鍊表反轉的3中方法。除此之外還想寫一些鍊表的簡單操作。
何為快慢指針，即對鍊表進行兩個不同步頻的指針標記遍歷。最經典的是慢指針走一步，快指針走兩步。
快慢指針有很多的應用，比如說：
1.判斷一個鍊表是否存在環。
兩個指針並排走，如果有環的話快指針最終會指向慢指針的位置。沒有環的話，快指針會指向None後退出。
當然這道題的解法不止這一樣，還可以利用set進行判斷。
2.輸出鍊表中的倒數第K個節點
這道題利用快慢指針的思路是這樣的。定義兩個指針，第一個指針向前走k-1步；第2個指針保持不動；到第k步時第2個指針也開始移動。由於兩個指針始終保持著k-1的距離，所以當快指針到達末尾時，慢指針剛好指向倒數第k個。
鍊表的技巧總結
技巧一 ：理解指針或者引用的含義
看懂鍊表結構不是很難，但是一旦把它和指針混在一起，就很容易讓人摸不著頭腦，（我再寫代碼的時候就出現了這種情況），所以要想寫對鍊表代碼，首先要理解好指針。
實際上，對於指針的理解，你只需要記住下面這句話就可以了：將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針，或者反過來說，指針中存儲了這個變量的內存地址，指向了這個變量，通過指針就能找到這個變量。
技巧二：警惕指針丟失和內存洩露
在寫鍊表代碼的時候，經常會找不到指針（引用）指到了哪兒，會弄丟了指針。
例如在單向鍊表中插入節點x，前節點是p，後節點是b。
p.next = x ;
x.next = p.next;
這樣就會導致指針丟失和內存洩露。如果把兩行代碼的順序顛倒一下，就不會丟失指針，要先將x.next指向b，然後，在將p的next節點指向x，這樣才不會丟失指針導致內存洩露。
技巧三：利用哨兵簡化實現的難度
哨兵，解決的是國家之間的邊界問題。同理，這裡說的哨兵也是解決"邊界問題"的，不直接參與業務邏輯。（還不是很了解，之後再補充）。
技巧四：重點留意邊界條件處理
軟體開發中，代碼在處理一些邊界問題或者異常情況中，容易出現bug。鍊表代碼也是容易產生bug，要想實現沒有bug的鍊表代碼，一定要在編寫的過程中以及在編寫完之後，檢查邊界條件是否考慮的全面，以及代碼在邊界條件下是否能正常運行。
經常用來檢查鍊表代碼是否正確的邊界條件有如下幾個：
如果鍊表為空，代碼是否能正常運行？
如果鍊表只包含一個節點時，代碼是否正常運行？
如果鍊表只包含兩個節點時，代碼是否正常運行？
代碼在處理頭節點和尾節點時，代碼是否正常運行？
我們在寫代碼的時候也不要只是實現業務邏輯就完事，也要多考慮會遇到哪些邊界問題或者異常情況，遇到了應該如何解決，這樣寫出來的代碼才會健壯。
比如鍊表為空、比如只包含一個結點或兩個節點的情況。比如處理頭結點和尾節點時，代碼是否正確。
再就是多寫多練了，這裡給出java語言實現的鍊表代碼。
技巧五：舉例畫圖，輔助思考
舉例畫圖，這個太有用了，我再學習算法的過程中，有時候看不懂實現代碼的時候，就想著如何通過畫圖來分解代碼的實現步驟，感謝在學習中，幫助過我的朋友，讓我能夠理解實現的過程。
在這裡繼續用上述的有序鍊表的合併的代碼：
畫圖輔助思考：
我們可以看到這個代碼裡就體現了邊界問題的幾個步驟：
1、首先是鍊表為空時的處理。
2、鍊表頭的處理。
3、鍊表多節點的處理。
4，鍊表尾的處理。
而圖中的舉例也正是對代碼實現的分解的很好的解釋。（畫圖輔助真的很棒）
技巧六：多謝多練，沒有捷徑
就是把常見的鍊表操作都自己多寫幾遍。最開始我都是遇到了各種各樣的不理解，甚至對於鍊表的操作都有些迷糊，但是多出問題多調試，慢慢的我們也能孰能生巧。唯手熟爾！
常見的鍊表操作，只要能熟練的寫出來，不熟就多寫幾遍，保證之後就不會再害怕寫鍊表代碼。
單鍊表反轉
檢測鍊表中的環
兩個有序鍊表的合併
刪除鍊表中倒數第K個節點
球鍊表的中間節點
寫出正確鍊表代碼的六個技巧。分別是理解指針或引用的含義、警惕指針的丟失和內存洩露，利用哨兵簡化實現難度，重點留意邊界條件處理，以及舉例畫圖，輔助思考，還有就是多寫多練，唯手熟爾。
勤能補拙，生活就是養成遊戲，勤練內功，即使當前不能花裡胡哨，未來也會強壯到無人能敵！
1、尋找鍊表的中間節點：最簡單的方法是，先遍歷一遍鍊表，計算出鍊表的長度，然後計算出中間節點的位置，然後再遍歷一遍，邊遍歷邊計算，直到找到中間節點，這個方法略顯囉嗦，最壞的情況需要遍歷2次鍊表，代碼如下：
另一個更靈巧的方法是，用兩個指針，慢指針每次走一步，快指針每次走兩步，當快指針走到鍊表的末端（NULL）時，慢指針正好指向了中間節點，代碼如下：
2、檢測鍊表是否有環：經典的做法也是用快慢指針，如果沒有環，快指針一定先到達鍊表的末端（NULL），如果有環，快、慢指針一定會相遇在環中，代碼如下：
3、檢測環的入口：經典的做法是先檢測是否有環，如果有環，則計算出環的長度，然後使用前後指針（不是快慢指針），所謂的前後指針就是一個指針先出發，走了若干步以後，第二個指針也出發，然後兩個指針一起走，當前後指針相遇時，它們正好指向了環的入口，代碼如下：
如果允許使用額外的內存，可以有更簡單的做法，即一邊遍歷，一邊將節點放在map中，當某個節點第二次出現在map中時，它就是入口節點，代碼如下：
4、鍊表翻轉：假設原鍊表為1->2->3，翻轉以後的鍊表應該是1<-2<-3，即節點3變成了頭節點，代碼如下：
5、刪除鍊表中的節點，注意這裡只給出要刪除的那個節點，不給出鍊表頭(假設被刪除節點不是尾節點)，代碼如下：
如果被刪除節點是尾節點，上面的代碼就無法將target上一個節點的next置為NULL，所以只有給了頭節點後，才能遍歷到target的上一個節點，並把其next置為NULL。
6、回文鍊表的檢測：所謂回文鍊表，即鍊表元素關於中間對稱，，如1->2->3->2->1，比較簡單的方法是用一個棧，先順序遍歷鍊表，並把每個節點放入棧中，遍歷完成後，棧的出棧順序正好是原鍊表的逆，代碼如下：
上面代碼的空間複雜度為O(N)，其實還有空間複雜度為O(1)的算法，也很靈巧，運用了之前提到的一些技巧，代碼如下：
這個方法的缺點是修改了原鍊表，但是綜合運用了鍊表的很多技巧，值得收藏。
7、合併有序鍊表：基本思路跟合併有序數組一樣，但是不需要O(N)的空間複雜度了，只需要O(1)的空間複雜度，代碼如下：
其實如果不要求空間複雜度為O(1)，可以用遞歸的思想，代碼更簡略，如下：
8、鍊表排序：如果沒有空間複雜度、時間複雜度的要求，那可選的方法太多了，像插入排序、選擇排序、冒泡排序，但是如果要求時間複雜度為O(NlogN)，而且空間複雜度為O(1)呢？歸併排序！！！正好可以用上剛剛寫的合併有序鍊表的代碼，代碼如下：
9、鍊表的循環右移：舉例如下1->2->3->4->5->NULL，循環右移2位後，變成了4->5->1->2->3->NULL，可以這麼考慮，如果鍊表的長度為N，循環右移K位，那麼等效於循環右移 K%N位，K%N是一個小於N的數，然後我們只需要找到循環右移後的頭節點即可，上面的例子就是4，然後直接把1->2->3連結到4->5->的後面，代碼如下：
10、以組為單位翻轉鍊表：組的長度用K表示，比如原鍊表為1->2->3->4->5，當K=2時，翻轉的結果為2->1->4->3->5，當K=3時，翻轉的結果為3->2->1->4->5，即先翻轉K個，再翻轉K個，當剩下的節點數小於K時，就不用翻轉了。用遞歸的方法很容易實現，代碼如下：
這個算法的空間複雜度為O(N/K)，即正比於遞歸深度，如果要求空間複雜度為O(1)呢？其實也比較簡單，只要循環處理每一段長度為K的鍊表，處理的時候注意保存上一段鍊表的尾節點，代碼如下：
11、翻轉鍊表的相鄰節點，比如原鍊表為1->2->3->4，翻轉後為2->1->4->3，這個其實就是上一道題的特例，即K=2，也要求空間複雜度為O(1)，不過還是遞歸簡潔啊，這裡只給出遞歸的代碼：
12、刪除鍊表的倒數第N個節點，要求只遍歷一次，還記得檢測環的入口嗎？是的，用前後指針，前後指針需要相隔（N+1）步，這樣當前指針為NULL的時候，後指針正好指向倒數第（N+1）個節點，然後直接刪除倒數第N個節點即可，代碼如下：
13、刪除有序鍊表中的重複元素，如原鍊表為1->2->3->3->4->4->5，刪除後的鍊表為1->2->5，這道題的關鍵是如果某節點有重複，務必將其全部刪掉，所以要對有重複的節點做個標記，代碼如下：
技巧：啞變量的引入使得頭結點不再具有特殊性，從而簡化處理流程。
14、像快排那樣將鍊表分成前後兩個部分，比如原鍊表為1->4->3->2->5->2，給出數字3，那麼鍊表中比3小的放在前面，比3大（或等於3）的放在鍊表的後面，處理後的鍊表應該是這樣的1->2->2->4->3->5，注意，4和5都大於3，那麼處理後的鍊表中4仍然應該在5的前面，代碼如下：
15、合併K個有序鍊表，這個咋一聽很簡單，先合併第1個、第2個，然後將合併後的結果與第3個合併，然後將合併的結果與第4個合併……，假設每個鍊表的長度為N，那麼時間複雜度為O（NK²），N為總的節點數，因為要合併K次。其實有更優的時間複雜度，我們可以先兩兩合併，即第1個與第2個合併，第3個與第4個合併，即執行K/2次合併，這作為第一輪合併，時間複雜度為O(KN)，接下來就只需要合併K/2個有序鍊表了，即進行第二輪合併，這樣總共需要進行logK輪合併，每一輪的時間複雜度為O(KN)，所以總的時間複雜度為O(NKlogK)，代碼如下（合併兩個有序鍊表的代碼已經在前面給出）：
16、尋找兩個鍊表的第一個公共節點，即兩個鍊表從某個節點開始合併了，我們要找出這個節點，經典的方法是先計算兩個鍊表的長度：L1，L2，假設L1>L2，那麼公共節點一定不在鍊表1的前（L1-L2）個節點中，這樣我們就可以讓鍊表1的頭節點指向第（L1-L2+1）個節點，然後同時推進兩個鍊表的頭節點，邊推進邊比較，直到遇到同一個節點，代碼如下：
17、鍊表的插入排序，這個就很直白了，代碼如下：
18、把有序鍊表轉換成一個儘量平衡的二叉樹，其實所謂的儘量平衡，就是把鍊表的中間節點作為根節點，根節點左邊的鍊表是樹的左子樹，根節點右邊的鍊表是樹的右子樹，然後問題就轉換成了原問題的子問題，即用前半段鍊表建立一個儘量平衡的左子樹，用後半段鍊表建立一個儘量平衡的右子樹，代碼如下：
19、在鍊表上模擬加法運算，比如(2 -> 4 -> 3) + (5 -> 6 -> 5)=7 -> 0 -> 9，鍊表的頭節點為個位，然後是十位……其實模擬的關鍵就是處理進位，代碼如下（略長，但比較直白）：
信息整理自網絡
實踐出真知▼