题解 | 判断一个链表是否为回文结构

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
 if (!head || !head->next) return true;
        
        // 步骤1：使用快慢指针找到链表中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 步骤2：反转后半部分链表
        ListNode* secondHalf = reverseList(slow->next);
        
        // 步骤3：比较前后两部分
        ListNode* first = head;
        ListNode* second = secondHalf;
        bool result = true;
        
        while (second) {
            if (first->val != second->val) {
                result = false;
                break;
            }
            first = first->next;
            second = second->next;
        }
        
        // // 步骤4：恢复链表（可选）
        // reverseList(secondHalf);
        
        return result;
    }
    
private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* current = head;
        while (current) {
            ListNode* nextTemp = current->next;
            current->next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }
};

方法一：将链表值复制到数组中（简单直观）
方法二：反转后半部分链表（优化空间）
只有两种正确的组合：
while (fast && fast->next) + 反转 slow
所有节点都参与比较
中间节点与自己比较（奇数）或中间两个节点互相比较（偶数）

while (fast->next && fast->next->next) + 反转 slow->next
中间节点不参与比较
更符合回文的直观理解

方法三：递归解法
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
private:
    ListNode* front;  // 全局指针，指向链表开头
    
public:
    bool isPail(ListNode* head) {
        front = head;  // 初始化全局指针指向链表头
        return recursivelyCheck(head);  // 开始递归检查
    }
    
private:
    bool recursivelyCheck(ListNode* current) {
        // 基本情况：到达链表末尾
        if (current == nullptr) {
            return true;
        }
        
        // 1. 递归调用：深入到链表末尾
        if (!recursivelyCheck(current->next)) {
            return false;  // 如果子调用发现不匹配，直接返回false
        }
        
        // 2. 回溯时比较当前节点和front指向的节点
        if (front->val != current->val) {
            return false;  // 值不匹配，不是回文
        }
        
        // 3. 移动front指针到下一个节点
        front = front->next;
        
        // 4. 当前节点匹配，返回true
        return true;
    }
};