链表回文判断实现求助：现有代码无法通过测试用例1->1->2->1

你的代码核心问题出在反转函数直接修改了原链表的结构，导致后续比较时，初始的head链表已经被破坏，无法和反转后的链表完成完整对比。

具体分析测试用例 1->1->2->1 #

当你调用reverse(head)时，原链表的指针被彻底修改：

• 原链表第一个节点（值为1）的next被设置为NULL
• 反转后的链表temp是1->2->1->1
  这时候你再用head（此时指向原第一个节点，next为NULL）和temp比较，循环只会执行1次，只对比了第一个节点的值就结束了，完全没检查后面的1->2->1部分，自然会错误地返回true，但实际上这个测试用例并非回文。

最优修复思路（空间复杂度O(1)） #

我们可以采用快慢指针找中点 + 反转后半部分链表 + 前后对比的方法，这种方法不会破坏原链表（可选恢复），且空间效率更高：

ListNode* reverse(ListNode* head) {
    ListNode* curr = head;
    ListNode* prev = NULL;
    while (curr != NULL) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return true;
        
        // 快慢指针找链表中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 反转后半部分链表
        ListNode* secondHalf = reverse(slow->next);
        ListNode* firstHalf = head;
        
        // 对比前后两部分的值
        bool isPalin = true;
        ListNode* temp = secondHalf;
        while (temp != NULL) {
            if (firstHalf->val != temp->val) {
                isPalin = false;
                break;
            }
            firstHalf = firstHalf->next;
            temp = temp->next;
        }
        
        // 可选：恢复原链表结构（如果不需要保留原链表可省略）
        slow->next = reverse(secondHalf);
        
        return isPalin;
    }
};

为什么这样能解决问题？ #

1. 快慢指针精准定位到链表中点，只反转后半部分，不会破坏前半部分的原始结构
2. 对比前半部分和反转后的后半部分，能准确判断整个链表是否为回文
3. 最后可以通过再次反转后半部分，恢复原链表的初始状态

另一种简单修复方式（空间复杂度O(n)） #

如果你坚持要反转整个链表，需要先复制原链表，再反转复制后的链表进行对比，避免破坏原链表：

// 新增链表复制函数
ListNode* copyList(ListNode* head) {
    if (head == NULL) return NULL;
    ListNode* newHead = new ListNode(head->val);
    ListNode* curr = newHead;
    ListNode* origCurr = head->next;
    while (origCurr != NULL) {
        curr->next = new ListNode(origCurr->val);
        curr = curr->next;
        origCurr = origCurr->next;
    }
    return newHead;
}

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return true;
        
        ListNode* copiedHead = copyList(head);
        ListNode* reversedHead = reverse(copiedHead);
        
        ListNode* orig = head;
        ListNode* rev = reversedHead;
        bool isPalin = true;
        while (orig != NULL && rev != NULL) {
            if (orig->val != rev->val) {
                isPalin = false;
                break;
            }
            orig = orig->next;
            rev = rev->next;
        }
        
        // 释放复制链表的内存，避免内存泄漏
        ListNode* temp;
        while (reversedHead != NULL) {
            temp = reversedHead;
            reversedHead = reversedHead->next;
            delete temp;
        }
        
        return isPalin;
    }
};

这种方法逻辑更简单，但需要额外的O(n)空间存储复制的链表，效率略低于第一种方案。

内容的提问来源于stack exchange，提问作者TUSHAR SAXENA