🔗 Linked List

指標操作、快慢指針與虛擬頭節點。

29 題 · 1 篇導讀

📖 分類導讀

鏈結串列是由節點透過指針相連的線性資料結構。不支援隨機存取，但插入和刪除操作為 O(1)。

Notes:

  • Dummy head node 可以大幅簡化邊界處理
  • 快慢指針是鏈結串列題目的核心技巧
  • 修改指針時要小心順序，避免斷鏈

單向 vs 雙向

  • 單向 (singly)：每個節點只有 next。省空間，但只能往後走，刪除某節點得先拿到它的前驅。
  • 雙向 (doubly)：節點有 prev 與 next，常再配一個 tail。支援雙向遍歷、O(1) 刪除已知節點，是 LRU 快取等設計題的基礎。

WARNING

鏈結串列沒有隨機存取：取第 k 個節點得從 head 走 k 步（O(k)），不像陣列能 O(1) 索引。這也是為什麼很多陣列題的雙指針技巧，在鏈結串列上要改用「快慢指針」實現。

指針操作心法

改指針前先在紙上畫出「改之前」與「改之後」的箭頭，並特別當心：

  • 順序：要接的新指針先存好，再斷舊指針，否則節點會遺失。反轉串列的 next = cur.next; cur.next = prev 就是這個道理。
  • Dummy head：在真正的頭前面加一個哨兵節點，能讓「刪除頭節點」「合併時的起點」等邊界與一般情況統一處理。
  • 哨兵 (sentinel) 思維同樣適用於迴圈：在尾端放一個保證匹配的標記，可省去「是否到結尾」的反覆判斷。
fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var cur = head
    while (cur != null) {
        val next = cur.next   // 先存好後繼
        cur.next = prev       // 反轉指向
        prev = cur            // 整體前移
        cur = next
    }
    return prev
}

本章深入

跨倉庫導讀

📘Fast & Slow Pointers
#2Add Two NumbersMedium★★★★★⏱ O(max(n, m))#19Remove Nth Node From End of ListMedium★★★★★⏱ O(n)#21Merge Two Sorted ListsEasy★★★★★⏱ O(n + m)#23Merge k Sorted ListsHard★★★★★⏱ O(N log k)#24Swap Nodes In PairsMedium★★★★★⏱ O(n)#25Reverse Nodes in k-GroupHard★★★★★⏱ O(n)#61Rotate ListMedium★★★★★⏱ O(n)#83Remove Duplicates From Sorted ListEasy★★★★★⏱ O(n)#86Partition ListMedium★★★★★⏱ O(n)#92Reverse Linked List IIMedium★★★★★⏱ O(n)#138Copy List with Random PointerMedium★★★★★⏱ O(n)#141Linked List CycleEasy★★★★★⏱ O(n)#143Reorder ListMedium★★★★★⏱ O(n)#146LRU CacheMedium★★★★★⏱ O(1)#147Insertion Sort ListMedium★★★★★⏱ O(n^2)#148Sort ListMedium★★★★★⏱ O(n log n)#160Intersection of Two Linked ListsEasy★★★★★⏱ O(m + n)#203Remove Linked List ElementsEasy★★★★★⏱ O(n)#206Reverse Linked ListEasy★★★★★⏱ O(n)#234Palindrome Linked ListEasy★★★★★⏱ O(n)#287Find the Duplicate NumberMedium★★★★★⏱ O(n)#460LFU CacheHard★★★★★⏱ O(1)#622Design Circular QueueMedium★★★★★⏱ O(1)#707Design Linked ListMedium★★★★★⏱ O(n)#725Split Linked List in PartsMedium★★★★★⏱ O(n + k)#876Middle of the Linked ListEasy★★★★★⏱ O(n)#1472Design Browser HistoryMedium★★★★★⏱ O(1)#1721Swapping Nodes in a Linked ListMedium★★★★★⏱ O(n)#2130Maximum Twin Sum Of A Linked ListMedium★★★★★⏱ O(n)