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

/**
 * 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) {
        if (!head ||
                !head->next) return true; // 空链表或只有一个节点，直接返回true

        ListNode* slow = head, *fast = head;
        while (fast->next && fast->next->next) { // 快慢指针找到中点
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* secondHalf = reverseList(slow->next); // 反转后半部分链表，中间值不包含在后面的链表
        ListNode* p1 = head;
        ListNode* p2 = secondHalf;

        bool result = true;
        while (result && p2) { // 比较前半部分和反转后的后半部分
            if (p1->val != p2->val) result = false;
            p1 = p1->next;
            p2 = p2->next;
        }

        slow->next = reverseList(secondHalf); // 恢复链表原状
        return result;
    }

// 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};

// 思路是找到后半段链表，将其翻转，然后挨个对比原链表，当值不同时则不是回文链表