Linked List - 鏈表

Linked List - 鏈表

鏈表是線性表(linear list)的一種。線性表是最基本、最簡單、也是最常用的一種資料結構。線性表中數據元素之間的關係是一對一的關系，即除了第一個和最後一個數據元素之外，其它數據元素都是首尾相接的。線性表有兩種儲存方式，一種是順序儲存結構，另一種是鏈式儲存結構。我們常用的陣列(array)就是一種典型的順序儲存結構。

相反，鏈式儲存結構就是兩個相鄰的元素在記憶體中可能不是物理相鄰的，每一個元素都有一個指標，指標一般是儲存著到下一個元素的指標。這種儲存方式的優點是已知插入位置時，定點插入和定點刪除的時間複雜度為 O(1)，不會浪費太多記憶體，添加元素的時候才會申請記憶體空間，刪除元素會釋放記憶體空間。缺點是訪問的時間複雜度最壞為 O(n)。

順序表的特性是隨機讀取，也就是循下標訪問(call-by-index)一個元素的時間複雜度是O(1)，鏈式表的特性是插入和刪除的時間複雜度為O(1)。

鏈表就是鏈式儲存的線性表。根據指標域的不同，鏈表分為單向鏈表、雙向鏈表、循環鏈表等等。

程式碼實現

Python

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

C++

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int val, ListNode *next=NULL):val(val),next(next){}
};

Java

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

鏈表的基本操作

反轉單向鏈表(singly linked list)

鏈表的基本形式是：1 -> 2 -> 3 -> null，反轉需要變為 3 -> 2 -> 1 -> null。這裡要注意：

訪問某個節點 curt.next 時，要檢驗 curt 是否為 null。
要把反轉後的最後一個節點（即反轉前的第一個節點）指向 null。

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域的交換，還需要注意的是目前節點和上一個節點的遞推。

Python

class DListNode:
    def __init__(self, val):
        self.val = val
        self.prev = self.next = null
    def reverse(self, head):
        curt = None
        while head:
            curt = head
            head = curt.next
            curt.next = curt.prev
            curt.prev = head
        return curt

Java

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。

鏈表指標的強健性(robustness)

綜合上面討論的兩種基本操作，鏈表操作時的強健性問題主要包含兩個情況：

當訪問鏈表中某個節點 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 即新的鏈表。

快慢指標(fast/slow pointer)

快慢指標也是一個可以用於很多問題的技巧。所謂快慢指標中的快慢指的是指標向前移動的步長，每次移動的步長較大即為快，步長較小即為慢，常用的快慢指標一般是在單向鏈表中讓快指標每次向前移動2，慢指標則每次向前移動1。快慢兩個指標都從鏈表頭開始遍曆，於是快指標到達鏈表末尾的時候慢指標剛好到達中間位置，於是可以得到中間元素的值。快慢指標在鏈表相關問題中主要有兩個應用：

快速找出未知長度單向鏈表的中間節點
設置兩個指標 *fast、*slow 都指向單向鏈表的頭節點，其中*fast的移動速度是*slow的2倍，當*fast指向末尾節點的時候，slow正好就在中間了。此方法可以有效避免多次遍歷鏈表
判斷單向鏈表是否有環
利用快慢指標的原理，同樣設置兩個指標 *fast、*slow 都指向單向鏈表的頭節點，其中 *fast的移動速度是*slow的2倍。如果 *fast = NULL，說明該單向鏈表以 NULL結尾，不是循環鏈表；如果 *fast = *slow，則快指標追上慢指標，說明該鏈表是循環鏈表。

Python

class NodeCircle:
    def __init__(self, val):
        self.val = val
        self.next = None
    def has_circle(self, head):
        slow = head
        fast = head
        while (slow and fast):
            fast = fast.next
            slow = slow.next
            if fast:
                fast = fast.next
            if fast == slow:
                break
        if fast and slow and (fast == slow):
            return True
        else:
            return False