鏈表（LinkedList）解題總結
鏈表基礎知識
定義
鏈表（Linked List）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針（Pointer）。
鏈表的操作
| 操作 | 時間複雜度 |
|---|---|
| 查找 | O(n) |
| 插入 | O(1)(僅插入本身，加上查找就是O(n)) |
| 刪除 | O(1)(僅刪除本身，加上查找就是O(n)) |
鏈表類型
| 鏈表類型 | 定義 |
|---|---|
| 單鏈表 | 節點只有一個指針，指向後繼節點 |
| 雙鏈表 | 節點有兩個指針，一個指向前置節點，一個指向後繼節點 |
| 循環鏈表 | 鏈表首尾相連 |
口訣
解題口訣：一個原則，兩個考點，兩個技巧，三個注意
一個原則
一個原則：畫圖！畫圖！畫圖！重要的事情要說三遍。鏈表的題目很容易把人繞暈，通過畫圖能夠很思路理清，不容易弄錯。
畫圖時要聚焦子結構，忽略其他資訊。
兩個考點
鏈表的題目絕大多數圍繞是這兩種類型：
- 指針的修改
- 鏈表的拼接
兩個技巧
- 虛擬頭：用一個虛擬頭指向頭節點，虛擬頭就是新的頭節點了，而虛擬頭不是題目給的節點，不參與運算，因此不需要特殊判斷
- 快慢指針：搞兩個指針，一個大步走（一次走兩步），一個小步走（一次走一步）
三個注意
即使畫圖，思路也正確了，也要注意以下三點：
- 出現了環，造成死循環
- 分不清邊界，導致邊界條件出錯
- 搞不懂遞歸怎麼做
解題技巧
快取
使用數組 / map 來快取鏈表中結點的資訊。這種方法有點賴皮，考察鏈表的時候，實際上不希望使用這種方式來解決。
快慢指針
一快（一次2步）一慢（一次1步）從頭節點出發。對於判斷是否有環、找中間節點等問題很有效。
題目包括：
雙指針
一前一後從頭節點出發，或者一頭一尾往中間走。對於判斷倒數第N個節點、反轉鏈表等問題特別有效。
遞歸
鏈表問題都可以分割成幾個相同的子問題以縮小問題規模，再通過調用自身返回局部問題的答案從而來解決大問題的。
題目包含：
