給定一個單向鏈結串列的頭節點
head，判斷該鏈結串列是否為回文（palindrome）。
Example:
Input: head = [1,2,2,1] Output: true
Intuition
TIP
核心思路：找到中點後反轉後半段，再逐一比對前半段與反轉後的後半段。
- 回文的特性是前後對稱，但單向鏈結串列只能往前走
- 方法一：用 Stack 或陣列存所有值，再雙向比對
- 方法二：快慢指針找中點 + 反轉後半段，O(1) 空間
Approaches
1. Stack — O(n) / O(n)
- Idea: 將所有節點值壓入 Stack，再從頭遍歷同時從 Stack 彈出比對
- Time:
O(n) - Space:
O(n)- Stack 儲存所有節點值
class Solution {
fun isPalindrome(head: ListNode?): Boolean {
val stack = ArrayDeque<Int>()
var curr = head
while (curr != null) {
stack.addLast(curr.`val`)
curr = curr.next
}
curr = head
while (curr != null) {
if (curr.`val` != stack.removeLast()) return false
curr = curr.next
}
return true
}
}⭐ 2. Fast-Slow Pointer + Reverse — O(n) / O(1)
- Idea: 快慢指針找中點，反轉後半段鏈結串列，再逐一比對
- Time:
O(n) - Space:
O(1)- 只用指針變數
class Solution {
fun isPalindrome(head: ListNode?): Boolean {
// 快慢指針找中點
var slow = head
var fast = head
while (fast?.next != null) {
slow = slow?.next
fast = fast.next?.next
}
// 反轉後半段
var prev: ListNode? = null
var curr = slow
while (curr != null) {
val next = curr.next
curr.next = prev
prev = curr
curr = next
}
// 比對前半段與反轉後的後半段
var left = head
var right = prev
while (right != null) {
if (left?.`val` != right.`val`) return false
left = left.next
right = right.next
}
return true
}
}WARNING
面試時可能會被問到是否需要還原鏈結串列。若需要，在比對完成後再反轉一次後半段即可。
🔑 Takeaways
- Pattern: 快慢指針找中點 + 鏈結串列反轉，是鏈結串列回文判斷的經典組合
- Key trick: 快慢指針停下時，slow 剛好在中間（奇數長度）或後半段起點（偶數長度），可以直接從 slow 開始反轉