目錄

題目

快慢雙指針步驟

讀者可能的錯誤寫法

正確的寫法

---

題目

234. 回文鏈表 - 力扣（LeetCode）

快慢雙指針步驟

找到鏈表的中點（find_mid函數）：

• 使用快慢指針，慢指針每次走一步，快指針每次走兩步

• 當快指針到達末尾時，慢指針指向中點

反轉鏈表后半部分（reserve函數）：

• 從中點開始，將后半部分鏈表反轉

• 返回反轉后的鏈表頭（原鏈表的尾部）

比較前半部分和反轉后的后半部分：

• 從原鏈表頭和反轉后的鏈表頭同時開始遍歷

• 逐個比較對應節點的值

• 如果任何一對值不相等，則不是回文

• 如果全部比較完畢都相等，則是回文

注意事項：

• 對于奇數長度鏈表，中點會被包含在后半部分

• 比較時需要同時檢查兩個指針是否為空，避免空指針訪問

• 理想情況下，比較完成后應該將鏈表還原（題目中沒有實現）

讀者可能的錯誤寫法

class Solution {
public:ListNode* find_mid(ListNode* head){ListNode* slow = head;ListNode* fast = head;while(fast){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reserve(ListNode* head){ListNode* phead = head;ListNode* newhead = nullptr;while(phead){ListNode* temp = phead->next;phead->next = newhead;newhead = phead;phead = temp;}return newhead;}bool isPalindrome(ListNode* head) {ListNode* mid = find_mid(ListNode* head);ListNode* res = reserve(ListNode* head);while(res){if(mid->val != res->val){return false;}mid = mid->next;res = res->next;}return true;}
};

你的代碼有幾個錯誤：

在調用函數時不應該再次聲明參數類型：

???//?錯誤ListNode*?mid?=?find_mid(ListNode*?head);//?正確ListNode*?mid?=?find_mid(head);

find_mid?函數中的?fast?指針移動邏輯有問題，可能會導致空指針異常：

   // 錯誤while(fast){slow = slow->next;fast = fast->next->next; // 如果fast->next為空，這里會崩潰}// 正確while(fast && fast->next){slow = slow->next;fast = fast->next->next;}

在?isPalindrome?函數中，你反轉了整個鏈表，這會改變原始鏈表結構。正確的做法是只反轉后半部分鏈表：

   // 錯誤ListNode* res = reserve(ListNode* head);// 正確ListNode* res = reserve(mid);

你在比較時使用了?mid?和?res，但應該比較的是原鏈表的前半部分和反轉后的后半部分：

   // 錯誤while(res){if(mid->val != res->val)// 正確ListNode* curr = head;while(res){if(curr->val != res->val)

正確的寫法

class Solution {
public:ListNode* find_mid(ListNode* head){ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reserve(ListNode* head){ListNode *phead = head;ListNode* tail = nullptr;while(phead){ListNode* tmp = phead->next;phead->next = tail;tail = phead;phead = tmp;}return tail;}bool isPalindrome(ListNode* head) {ListNode* mid = find_mid(head);ListNode* res = reserve(mid);ListNode* cur = head;while(res){if(cur->val != res->val){return false;}cur = cur->next;res = res->next;}return true;}
};