能夠完賽的人是鬼吧
本文會提到做 singular linked list 常犯錯誤、如何避免，與常見的技巧。
此系列 Leetcode 篇不介紹基本資料結構。

常見錯誤：null pointer

通常在寫這類題目，就是個 while 起手式吧，然後取得下一個 linked list node。
寫完之後要檢查所有取 node.next 或 node.val 的地方，在現在這個 while 條件下，node 有沒有可能是 None，然後修改 while 條件。
當然可以一次想到位最好啦。
舉個例子

1 while fast and fast.next:
2            fast = fast.next.next
3            slow = slow.next

line 1: 取 fast 的 next
-> 需判斷此時 fast 不會為 None
-> while fast 才會進來這行，沒問題

line 2: 取 fast.next 的 next
-> 需判斷此時 fast.next 不會為 None
-> while fast.next 才會進來這行，沒問題。

line 3: 取slow 的 next
-> 需判斷此時 slow 不會為 None
-> 因為 slow 只會指到 fast 指過的，沒問題。

常見錯誤：linked list 斷掉

沒想清楚每一輪的步驟，導致 linked list 斷掉，下一輪拿不到接下來該處理的 node。
可以畫出來想。

常見錯誤：linked list 連出 cycle

這也是沒想好而已，就.. 畫出來想清楚
206. Reverse Linked List 這題可以注意一下。

使用 dummy node

時機

題目要回傳一個新的 linked list （head node）時。

用法

先用 dummy = ListNode() 開個空的，
然後依據題目狀況去連接 node，
最後 return dummy.next。

優點

可以少掉判斷到底哪個 node 是新的 head。
21. Merge Two Sorted Lists
206. Reverse Linked List

快慢指針

時機

1. 判斷 linked list 有沒有 cycle（141. Linked List Cycle）
2. 回傳 cycle 入口 node （142. Linked List Cycle II）。
3. 還有取得 linked list 中點時。例如要做 merge sort （148. Sort List）

核心想法

我覺得不太容易在第一次做就想到，所以稍微想過就可以去理解一下快慢指針做法。
以下是我的思考迴路：

1. 重複走到一個 node （n1）時，要怎麼透過另一個 node（n2） 知道我走過 n1？
2. 不存額外資訊的話，那只有當指到 n1 與 n2 的 p1 p2 相遇時，才能有所判斷處理吧？
   這裡不提那三種作法了，直接去看題目吧。

必須能證明

快慢指針為何能 work？
背後的數學證明（簡單就好）要能解釋、多想幾次，否則背答案是背不長久的。

LC 141 要能證明「fast pointer 會追到 slow pointer」：

1. fast 在 slow 後一步，下一步的時候就會相遇
2. fast 在 slow 後兩步，下一步的時候就會差一步，回到 1.

LC 142 要能證明「fast pointer 會和 slow pointer 在 cycle 入口相遇」
...我看明天會不會記得補圖

Recursive or Iterative?

蠻多 linked list 題目都可以用 recursive 的方式解出來。
但建議兩個都要能快速寫出來。
如果一開始想不到，或許 recursive 比較好下手，
但至少就要 O(n) 空間（遞迴深度的 stack frame），分析時要能想到。

總結

linked list 題目很建議要畫一下，憑空想容易犯上述的錯誤。
我快不行了。