鏈結串列 (Linked List) 的定義#

鏈結串列不需要連續的記憶體空間，通過「指標」將一組零散的記憶體塊串聯起來使用。

基本結構：

• 結點（Node）：記憶體塊
• 後繼指標（next）：指向下一個結點的地址
• 頭節點（head）：第一個結點，記錄鏈結串列基地址
• 尾結點（tail）：最後一個結點，next 指向 NULL

常見鏈結串列結構#

flowchart TB
    subgraph 單鏈結串列["單鏈結串列"]
        direction LR
        H1[Head] --> A1[A] --> B1[B] --> C1[C] --> N1[NULL]
    end

    subgraph 雙向鏈結串列["雙向鏈結串列"]
        direction LR
        N2[NULL] <--> A2[A] <--> B2[B] <--> C2[C] <--> N3[NULL]
    end

    subgraph 迴圈鏈結串列["迴圈鏈結串列"]
        direction LR
        A3[A] --> B3[B] --> C3[C] --> A3
    end

單鏈結串列#

每個結點只有一個 next 指標，指向下一個結點。

迴圈鏈結串列#

尾結點的 next 指向頭節點，形成環狀結構。適合處理環型結構資料，如約瑟夫問題。

雙向鏈結串列#

每個結點有兩個指標：

• next：指向下一個結點
• prev：指向前一個結點

雖然佔用更多記憶體，但支援雙向走訪，在某些場景下更高效。

鏈結串列 vs 陣列#

*鏈結串列插入/刪除為 O(1) 的前提是：已經找到操作位置。如果需要先查找，則還要加上 O(n) 的查找時間。

雙向鏈結串列的優勢#

前兩個場景，雙向鏈結串列都靠 prev 指標把原本需要走訪的操作壓到常數時間：

第三個場景是有序鏈結串列的按值查詢：可以記錄上次查找位置 p，根據目標值與 p 的大小關係決定往前或往後查找，平均只需查找一半資料。

設計思想：空間換時間。雙向鏈結串列用額外的記憶體空間（prev 指標）換取操作效率的提升。這是一個重要的設計原則：

• 記憶體充足 ➡️ 空間換時間
• 記憶體緊缺 ➡️ 時間換空間

LRU 快取實作#

問題： 如何用鏈結串列實作 LRU（Least Recently Used）快取淘汰策略？

策略：

• FIFO：先進先出
• LFU：最少使用
• LRU：最近最少使用

實作思路：

維護一個有序單鏈結串列，越靠近尾部的結點是越早存取的。

當有新資料被存取時：

flowchart TD
    A[存取資料] --> B{資料在快取中?}
    B -->|是| C[移動到頭部]
    B -->|否| D{快取已滿?}
    D -->|否| E[插入頭部]
    D -->|是| F[刪除尾結點]
    F --> E

    style C fill:#e8f5e9
    style E fill:#e3f2fd
    style F fill:#ffebee

1. 資料已在鏈結串列中 ➡️ 移到頭部
2. 資料不在鏈結串列中：
   • 快取未滿 ➡️ 插入頭部
   • 快取已滿 ➡️ 刪除尾結點，插入頭部

時間複雜度： O(n)（需要走訪查找）

引入雜湊表記錄每個資料的位置，將存取時間複雜度降到 O(1)。這就是「雜湊表 + 雙向鏈結串列」的 LRU 實作方式。

快慢指標在鏈結串列的應用#

鏈結串列無法像陣列那樣用索引隨機存取，很多問題不能直接「跳到第幾個」，只能靠兩個指標的相對位置來解。完整原理（為何相遇必判圈、如何防 null 等）在 雙指標 一節有完整展開，這裡聚焦快慢指標在鏈結串列上的三個經典應用。

找中間節點 ^↗#

快指標一次走兩步、慢指標一次走一步。快指標走到底時，慢指標正好停在中點。

fun middleNode(head: ListNode?): ListNode? {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
        slow = slow?.next
        fast = fast.next?.next
    }
    return slow
}

找倒數第 k 個節點 ^↗#

先讓快指標單獨走 k 步，再讓兩指標齊步前進。當快指標走到底時，慢指標所在的就是倒數第 k 個節點。

fun kthFromEnd(head: ListNode?, k: Int): ListNode? {
    var slow = head
    var fast = head
    repeat(k) { fast = fast?.next }   // 快指標先走 k 步
    while (fast != null) {
        slow = slow?.next
        fast = fast?.next
    }
    return slow
}

判斷是否有環 ^↗（Floyd）#

快慢指標同時出發，若鏈結串列有環，快指標終會在環內「追上」慢指標而相遇；若快指標走到 null，則無環。

fun hasCycle(head: ListNode?): Boolean {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
        slow = slow?.next
        fast = fast.next?.next
        if (slow === fast) return true   // 相遇即有環
    }
    return false
}

操作鏈結串列時有兩個常見地雷：

• null pointer：快指標一次跳兩步，迴圈條件務必同時檢查 fast != null && fast.next != null，否則 fast.next.next 會踩到空指標。
• 頭節點變動：刪除或插入頭節點時，記得更新 head，否則會丟失整條鏈結串列或讓 head 指向舊節點。

鏈結串列程式碼技巧#

理解指標的含義#

p.next = q              // p 的 next 指向 q 這個結點
p.next = p.next.next    // p 的 next 指向 p 的下下個結點

警惕指標丟失與記憶體洩漏#

錯誤示範：

p.next = x           // p 的 next 已經指向 x
x.next = p.next      // 相當於 x.next = x，鏈結串列斷裂！

正確順序：

x.next = p.next      // 先讓 x 指向下一個結點
p.next = x           // 再讓 p 指向 x

刪除結點時，C 語言需要手動釋放記憶體，否則會記憶體洩漏。（JVM 上的 Kotlin 有 GC 代勞，但仍要小心別讓已刪除的結點被其他引用意外「復活」。）

利用哨兵簡化邊界處理#

插入第一個結點和刪除最後一個結點需要特殊處理，很容易出錯。

解決方案： 使用帶頭鏈結串列（哨兵結點）。

哨兵結點不存儲資料，head 始終指向它，統一了所有操作的邏輯。

邊界條件檢查#

寫完程式碼後，用以下邊界條件測試：

• 鏈結串列為空
• 鏈結串列只有一個結點
• 鏈結串列只有兩個結點
• 處理頭節點和尾結點

畫圖輔助思考#

複雜的鏈結串列操作容易把自己繞暈。畫出操作前後的鏈結串列變化，對照著寫程式碼會清晰很多。

多寫多練#

常見的鏈結串列操作必須能熟練手寫：

1. 單鏈結串列反轉 ^↗
2. 鏈結串列中環的檢測 ^↗
3. 兩個有序鏈結串列合併 ^↗
4. 刪除鏈結串列倒數第 n 個結點 ^↗
5. 求鏈結串列的中間結點 ^↗

寫鏈結串列程式碼最考驗邏輯思維能力。指標操作、邊界處理稍有不慎就會出 Bug。這也是面試官喜歡考鏈結串列的原因。

小結#