234. Palindrome Linked List
判斷一條鏈結串列是不是回文。
思路
這一題是一道簡單的題目，可是其實很容易不小心踩到雷。
直覺解：反轉之後比對
第一個直覺的想法會是我們就把 Linked List 反轉，接著比較一下是不是都一樣就好。
可是這裡有個雷：如果我們要反轉 Linked List，第一件要做的事情會是我們要先複製一個原先的 Linked List —— 不然 Linked List 都是傳指標，反轉完原先的 Linked List 就沒了，根本沒東西可以拿來比對。
這個「反轉會就地破壞原本的資料」是鏈結串列題和陣列題最不一樣的地方。陣列可以 arr[::-1] 得到一份新的，串列的反轉預設是原地的。
只比一半就夠
不過這一題其實存在著更優的解法，雖然理論時間複雜度並沒有真的改變非常多，可是少使用了很多的記憶體。
回文的題目的特性之一，就是前後對稱，所以我們其實並不用比對到整個 Linked List，只要比對到一半就好。可是 Linked List 並沒有長度的概念，所以可以利用快慢指針的方式取得中間點（見 876. Middle of the Linked List）。
第二步就是我們從中間點到結尾的部分，反轉整個 Linked List（見 206. Reverse Linked List），這樣的話我們就會有兩個**「幾乎」**一模一樣的 Linked List。接下來和上面的部分一樣，一起齊步走，如果中間有一個位置發生不同的值，那就不是回文。
所以這題其實是兩個已知題拼起來的：找中點（876）+ 反轉（206）+ 齊步比對。面試時先把這三步講出來，再各自實作，比直接動手穩得多。
奇數長度要特判嗎
上面說「幾乎」一模一樣，就是在指這件事：回文的長度是奇數還是偶數，處理起來會不會不同？
不用特判。 但理由不是「中間那個元素沒被檢查到」—— 實際跑一遍會看到它有被檢查，只是拿自己跟自己比：
[1, 2, 3, 2, 1] 的比較過程
（node.val, head.val, 是不是同一個節點）
(1, 1, 不同節點)
(2, 2, 不同節點)
(3, 3, 同一個節點) ← 中間的 3，自己跟自己比，必然相等
因為 middleNode 在奇數長度時回傳的是正中間那一顆，它同時是「前半段的最後一顆」和「反轉後那段的最後一顆」。所以最後一輪比較的兩個指針指向同一個節點，必定相等，答案不受影響。
偶數長度時前後兩段長度相同，沒有這個交會點，更單純。兩種情況都不用寫額外的判斷，這是這個解法漂亮的地方。
解題方向
解法一：複製一份再反轉
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def cloneLinkedList(self, head) -> ListNode:
copy = copy_head = ListNode(0)
curr = head
while curr:
copy.next = ListNode(curr.val)
copy = copy.next
curr = curr.next
return copy_head.next
def reverseList(self, head: ListNode) -> ListNode:
node = None
while head:
tmp = head.next
head.next = node
node = head
head = tmp
return node
def isPalindrome(self, head: ListNode) -> bool:
cloned = self.reverseList(self.cloneLinkedList(head))
curr = head
while curr:
if curr.val != cloned.val:
return False
curr = curr.next
cloned = cloned.next
return True
cloneLinkedList 裡的 copy_head 是 dummy head，讓「接第一顆」不用寫特例。
解法二：找中點 + 反轉後半（ 空間）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
# 206. Reverse Linked List
def reverseList(self, head: ListNode) -> ListNode:
prev = None
while head:
tmp = head.next
head.next = prev
prev = head
head = tmp
return prev
# 876. Middle of the Linked List
def middleNode(self, head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def isPalindrome(self, head: ListNode) -> bool:
mid = self.middleNode(head)
node = self.reverseList(mid)
while node:
if node.val != head.val:
return False
node = node.next
head = head.next
return True
迴圈條件是 while node 而不是 while head —— 反轉後那一段比較短（或一樣長），用它當終止條件才不會走過頭。
補充
這個解法會破壞輸入
解法二把後半段就地反轉了，跑完之後從原本的 head 走出來只剩前半段。[1, 2, 3, 2, 1] 跑完會變成 [1, 2, 3]。
面試時這一定會被問：「你的函式改動了呼叫端的資料，這樣可以嗎？」主動說出來比被抓到好，而且復原很簡單 —— 把反轉過的那段再反轉一次接回去：
def isPalindrome(self, head: ListNode) -> bool:
mid = self.middleNode(head)
second = self.reverseList(mid)
node, curr = second, head
ok = True
while node:
if node.val != curr.val:
ok = False
break
node = node.next
curr = curr.next
self.reverseList(second) # 復原
return ok
注意這裡不能中途 return False 了，要用一個 ok 記著、跑完復原再回傳，否則提早離開就漏掉復原。
最短的寫法
如果不在意空間，把值全部倒進 list 再比對是最短的：
def isPalindrome(self, head: ListNode) -> bool:
vals = []
while head:
vals.append(head.val)
head = head.next
return vals == vals[::-1]
三行， 時間 空間，而且不會破壞輸入。面試時可以先寫這個確認方向，再說「如果要 空間我會改成找中點 + 反轉後半」—— 這樣的順序比一開始就寫複雜版更能展示思考過程。
相關題
876. Middle of the Linked List、206. Reverse Linked List 是這題的兩個零件；143. Reorder List 是另一個用同樣兩個零件拼起來的題目（找中點、反轉後半、交錯合併）。「找中點 + 反轉後半」是鏈結串列的一組常用組合技，見 Linked List 模板。
複雜度
倒進 list 比對
- 時間 — 一趟收集、一趟比對
- 空間 — 存下所有值
複製一份再反轉
- 時間 — 複製、反轉、比對各一趟
- 空間 — 完整複製一條串列（連節點物件都新建，比上一種更耗）
找中點 + 反轉後半
- 時間 — 找中點 、反轉 、比對
- 空間 — 只有幾個指針
其中 n 是節點數。
三者時間同級，差別完全在空間 —— 這也是題目 follow-up 問的（"Could you do it in O(n) time and O(1) space?"）。代價是它會就地修改串列，所以嚴謹的做法要加上復原。