LeetCode - 234. 回文链表

目录

题目

快慢双指针步骤

读者可能的错误写法

正确的写法

---

题目

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;}
};