36張圖帶你深刻理解鏈表
文章內容主要包括以下幾點：
什么是鏈表
單鏈表的基本操作：增、刪、改、查
LeetCode #206 反轉單列表
循環(huán)鏈表及LeetCode #141 環(huán)形鏈表檢測
雙向鏈表及其增加刪除操作
01
什么是鏈表
02
鏈表的基本操作：增、刪、改、查
由于鏈表的每個節(jié)點都存儲了下一個節(jié)點的指針，因此，要想在指定位置增加一個節(jié)點node，就需要知道指定位置的前一個節(jié)點。首先明確下幾個變量的含義：
變量prev——表示前一個節(jié)點，比如節(jié)點2的前一個節(jié)點就是節(jié)點1。
變量head——表示頭結點所在位置。
變量node——表示要添加的節(jié)點。
這時請思考一個問題，在剛才添加結點node到鏈表中時，執(zhí)行了兩個語句，分別是：node.next=prev.next和prev.next=node。那么，如果這兩個語句的執(zhí)行順序反過來是什么結果呢？
還是以下圖為例來進行說明，即將結點node添加到結點3所在的位置。
先執(zhí)行prev.next=node后，結果如下圖：
在執(zhí)行node.next=prev.next之后，結果如下圖。原因在于當執(zhí)行完prev.next=node之后，結點node成為了變量prev所指向的結點的下一個結點，因此在執(zhí)行node.next=prev.next時，結點node指向了自己。這時我們發(fā)現(xiàn)，鏈表斷開了。這是在鏈表操作中特別需要注意的一個地方，要小心別丟失了指針。
在將結點node添加到鏈表指定位置時，我們借助了變量prev——用以表示待添加結點所在位置的前一個節(jié)點。那么，如果我們是將結點node添加到頭結點head所在的位置，這時頭結點head之前沒有結點了，那改怎么辦呢？
這時就要介紹一個鏈表操作中常用的一個方法了：設置虛擬頭結點dummyHead，來簡化操作難度。
所謂虛擬頭結點就是一個只存儲下一個結點指針地址但不存儲任何元素信息的節(jié)點。虛擬頭結點的示例如下圖，在有了虛擬頭結點后，在向鏈表的頭結點head所在位置添加元素時，操作方式就和向鏈表其它位置添加元素統(tǒng)一起來了。
如果是向鏈表頭添加結點，則只需將新的結點的后繼指針指向當前鏈表的頭結點即可，時間復雜度是O(1)；
如果是向鏈表末尾添加結點，則需從頭遍歷鏈表直到尾部結點，因此此時的時間復雜度是O(n)；
如果是向鏈表任意位置添加結點，那么平均來看時間復雜度就是O(n)。
2.刪除鏈表指定位置的結點
刪除鏈表指定位置的結點，還是借助虛擬頭結點來簡化操作。如下圖，假設要刪除鏈表中第二個結點2。
首先，將變量prev向后移動一個位置，指向待刪除結點的前一個結點。
接著，執(zhí)行語句prev.next=delNode.next，即將變量prev所指向結點的后繼指針next指向待刪除結點的下一個結點，如下圖：
最后，執(zhí)行delNode.next=null就可將待刪除結點從鏈表中釋放，如下圖：
如果是刪除頭結點，則虛擬頭結點就是頭結點的前一個結點，因此時間復雜度是O(1)；
如果是刪除鏈表末尾添加結點，則需從頭遍歷鏈表直到尾部結點的前一個結點，因此此時的時間復雜度是O(n)；
如果是刪除鏈表中任意結點，那么平均來看時間復雜度就是O(n)。
3.修改鏈表指定位置結點的值
在修改鏈表指定位置結點的值時，可以不借助虛擬頭結點dummyHead了。我們用變量cur表示當前所考察的結點。比如，我們要修改鏈表中結點2的值，該怎么做呢？
首先，將變量cur指向待修改的那個結點，如下圖：
然后執(zhí)行cur.e=22(e表示當前結點數(shù)據(jù)域所存儲的元素值)就可將鏈表結點2的值修改為22。
由于鏈表不支持隨機訪問，因此要修改某個結點的值，只能從頭遍歷鏈表，找到要修改的結點，這個過程時間復雜度是O(n)。然后，修改值這一個動作的時間復雜度是O(1)，因此修改鏈表指定位置結點的值的時間復雜度整體是O(n)；
4.判斷鏈表中是否包含某個元素
判斷鏈表中是否包含某個元素，同樣可以不借助虛擬頭結點dummyHead。用變量cur表示當前考察的結點，然后依次遍歷鏈表中的每個結點，判斷當前考察的結點數(shù)據(jù)域所存儲的值是不是和目標值相等。
比如，我們要判斷鏈表中是否包含元素2，那么當變量cur指向下圖的結點時，就可以判定鏈表中包含元素2。
要判斷鏈表中是否包含某個元素，只能從頭遍歷鏈表，然后拿當前考察的結點數(shù)據(jù)域的值和目標值比對，因此時間復雜度整體上是O(n)；
03
來看如何寫出正確的鏈表代碼
LeetCode#206號題目是關于單鏈表反轉的，題目給出的示例是：
輸入:?1->2->3->4->5->NULL?
輸出:?5->4->3->2->1->NULL
LeetCode
對于剩余未考察的結點，重復上述步驟即可將鏈表反轉。
動畫演示
代碼實現(xiàn)
public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode cur = head;while (cur != null) {ListNode nextNode = cur.next;= prev;prev = cur;cur = nextNode;}return prev;}
循環(huán)鏈表
如果我們將單鏈表的尾結點的后繼指針由指向NULL改為指向單鏈表的頭結點，會是什么樣的呢？結果如下圖：
對于這種尾結點的后繼指針指向頭結點的單鏈表，我們稱之為循環(huán)鏈表。
接著看下LeetCode#141環(huán)形鏈表檢測這個問題，題目描述如下：
給定一個鏈表，判斷鏈表中是否有環(huán)。
如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。?為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從?0?開始）。?如果 pos 是?-1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進行傳遞，僅僅是為了標識鏈表的實際情況。?
如果鏈表中存在環(huán)，則返回 true 。?否則，返回 false 。
來源：力扣（LeetCode）
輸入：head =?[3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。
LeetCode
這里你可能會問為什么慢指針slow初始指向鏈表頭結點而快指針fast初始指向鏈表頭結點的下一個結點？
代碼實現(xiàn)
public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head.next;while (slow != fast) {if (fast == null || fast.next == null) {return false;}fast = fast.next.next;slow = slow.next;}return true;}
那代碼中為什么是慢指針slow每次向后移動一個位置，而快指針fast是向后移動兩個位置呢？如果fast也向后移動一個位置會是什么樣呢？
快指針fast每次向后移動兩個位置，如果鏈表中有環(huán)，就會先進入環(huán)，從而和慢指針slow相遇，但如果fast每次向后移動一個位置，那么它和慢指針slow之間，一直有一個結點距離，即使鏈表中有環(huán)，也不會相遇。
雙向鏈表
在單鏈表中由于每個結點都會存儲下一個結點的地址，因此，在單鏈表中查找下一個結點的時間復雜度是O(1)。但如果是要查找上一個結點，那么最壞時間復雜度就是O(n)了，因為每次都要從頭開始遍歷查找鏈表中的每個結點。
為了解決這個問題呢，就有了雙向鏈表。雙向鏈表是在單鏈表的基礎上，再設置一個指向其前驅結點的指針，如下圖。
由于雙向鏈表的結點有個前驅指針指向前一個結點，因此雙向鏈表支持在O(1)的時間復雜度下找到前驅結點。
雙向鏈表中添加結點
雙向鏈表初始如下圖，變量cur指向當前考察結點。我們看下如何在當前考察的結點之后添加結點node。
第一步先執(zhí)行node.prev=cur，即將變量cur指向的結點作為新增結點node的前驅結點。
第二步執(zhí)行node.next=cur.next，即將變量cur指向的結點的下一個結點作為新增結點node的下一個結點。
第三步執(zhí)行cur.next.prev=node，即將新增的結點node作為變量cur所指向的結點的下一個結點的前驅結點。
第四步執(zhí)行cur.next=node，即將新增結點作為當前考察結點的后繼結點。這時，就完成了將結點node添加到鏈表中這一操作。
同樣，對于上述四個步驟的執(zhí)行要注意先后順序，防止出現(xiàn)指針丟失的情況。
雙向鏈表中刪除結點
如下圖，假設現(xiàn)在要刪除變量cur所指向的結點，該怎么操作呢？
第一步，執(zhí)行cur.prev.next=cur.next，即將當前結點的下一個結點，作為當前結點前驅結點的后繼結點。
第二步執(zhí)行，cur.next.prev=cur.prev，即將當前結點的前一個結點，作為當前結點的后繼結點的前驅結點。
最后，執(zhí)行cur.prev=null，cur.next=null即可將當前結點與原有鏈表斷開。
