# Linked List - 鏈表 鏈表是線性表的一種。線性表是最基本、最簡單、也是最常用的一種數據結構。線性表中數據元素之間的關系是一對一的關系，即除了第一個和最后一個數據元素之外，其它數據元素都是首尾相接的。線性表有兩種存儲方式，一種是順序存儲結構，另一種是鏈式存儲結構。我們常用的數組就是一種典型的順序存儲結構。 相反，鏈式存儲結構就是兩個相鄰的元素在內存中可能不是相鄰的，每一個元素都有一個指針域，指針域一般是存儲著到下一個元素的指針。這種存儲方式的**優點**是插入和刪除的時間復雜度為 O(1)，不會浪費太多內存，添加元素的時候才會申請內存，刪除元素會釋放內存。缺點是訪問的時間復雜度最壞為 O(n)。 順序表的特性是隨機讀取，也就是訪問一個元素的時間復雜度是O(1)，鏈式表的特性是插入和刪除的時間復雜度為O(1)。 鏈表就是鏈式存儲的線性表。根據指針域的不同，鏈表分為單向鏈表、雙向鏈表、循環鏈表等等。 ### 編程實現 ### Java ~~~ public class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; this.next = null; } } ~~~ ### 鏈表的基本操作 ### 反轉鏈表 #### 單向鏈表 鏈表的基本形式是：`1 -> 2 -> 3 -> null`，反轉需要變為 `3 -> 2 -> 1 -> null`。這里要注意： - 訪問某個節點 curt.next 時，要檢驗 curt 是否為 null。 - 要把反轉后的最后一個節點（即反轉前的第一個節點）指向 null。 ~~~ class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } public ListNode reverse(ListNode head) { ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } ~~~ #### 雙向鏈表 和單向鏈表的區別在于：雙向鏈表的反轉核心在于`next`和`prev`域的交換，還需要注意的是當前節點和上一個節點的遞推。 ~~~ class DListNode { int val; DListNode prev, next; DListNode(int val) { this.val = val; this.prev = this.next = null; } } public DListNode reverse(DListNode head) { DListNode curr = null; while (head != null) { curr = head; head = curr.next; curr.next = curr.prev; curr.prev = head; } return curr; } ~~~ ### 刪除鏈表中的某個節點 刪除鏈表中的某個節點一定需要知道這個點的前繼節點，所以需要一直有指針指向前繼節點。還有一種刪除是偽刪除，是指復制一個和要刪除節點值一樣的節點，然后刪除，這樣就不必知道其真正的前繼節點了。 然后只需要把 `prev -> next = prev -> next -> next` 即可。但是由于鏈表表頭可能在這個過程中產生變化，導致我們需要一些特別的技巧去處理這種情況。就是下面提到的 Dummy Node。 ### 鏈表指針的魯棒性 綜合上面討論的兩種基本操作，鏈表操作時的魯棒性問題主要包含兩個情況： - 當訪問鏈表中某個節點 curt.next 時，一定要先判斷 curt 是否為 null。 - 全部操作結束后，判斷是否有環；若有環，則置其中一端為 null。 ### Dummy Node Dummy node 是鏈表問題中一個重要的技巧，中文翻譯叫“啞節點”或者“假人頭結點”。 Dummy node 是一個虛擬節點，也可以認為是標桿節點。Dummy node 就是在鏈表表頭 head 前加一個節點指向 head，即 dummy -> head。Dummy node 的使用多針對單鏈表沒有前向指針的問題，保證鏈表的 head 不會在刪除操作中丟失。除此之外，還有一種用法比較少見，就是使用 dummy node 來進行head的刪除操作，比如 Remove Duplicates From Sorted List II，一般的方法current = current.next 是無法刪除 head 元素的，所以這個時候如果有一個dummy node在head的前面。 所以，當鏈表的 head 有可能變化（被修改或者被刪除）時，使用 dummy node 可以很好的簡化代碼，最終返回 dummy.next 即新的鏈表。 ### 快慢指針 快慢指針也是一個可以用于很多問題的技巧。所謂快慢指針中的快慢指的是指針向前移動的步長，每次移動的步長較大即為快，步長較小即為慢，常用的快慢指針一般是在單鏈表中讓快指針每次向前移動2，慢指針則每次向前移動1。快慢兩個指針都從鏈表頭開始遍歷，于是快指針到達鏈表末尾的時候慢指針剛好到達中間位置，于是可以得到中間元素的值。快慢指針在鏈表相關問題中主要有兩個應用： - 快速找出未知長度單鏈表的中間節點 設置兩個指針 `*fast`、`*slow` 都指向單鏈表的頭節點，其中`*fast`的移動速度是`*slow`的2倍，當`*fast`指向末尾節點的時候，`slow`正好就在中間了。 - 判斷單鏈表是否有環 利用快慢指針的原理，同樣設置兩個指針 `*fast`、`*slow` 都指向單鏈表的頭節點，其中 `*fast`的移動速度是`*slow`的2倍。如果 `*fast = NULL`，說明該單鏈表 以 `NULL`結尾，不是循環鏈表；如果 `*fast = *slow`，則快指針追上慢指針，說明該鏈表是循環鏈表。