题解 | #链表的回文结构#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
*/

class PalindromeList {
  public:
    // 检查链表是否为回文
    bool chkPalindrome(ListNode* A) {
        // 如果链表为空，直接返回 false
        if (A == NULL)
            return false;

        // 使用快慢指针找到链表的中间节点
        ListNode* slow = A, *fast = A;
        while (fast && fast->next) {
            slow = slow->next;         // 慢指针每次移动一步
            fast = fast->next->next;   // 快指针每次移动两步
        }

        // 反转链表的后半部分
        ListNode* cur = NULL, *next = slow;
        while (slow) {
            next = slow->next;    // 暂存下一个节点
            slow->next =
                cur;     // 将当前节点的 next 指向前一个节点，完成反转
            cur = slow;           // 更新前一个节点为当前节点
            slow = next;          // 将当前节点移动到下一个节点
        }

        // 将next指针重新指向链表的头部，用于从头开始比较
        next = A;

        // 比较前半部分和反转后的后半部分的节点值
        while (cur) {
            if (next->val != cur->val) // 若节点值不相同，说明不是回文
                return false;
            next = next->next;         // 移动到下一个节点
            cur = cur->next;           // 反转部分也移动到下一个节点
        }

        // 若所有节点值都匹配，则链表为回文，返回 true
        return true;
    }
};