题解 | #牛群编号的回文顺序#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

链表，回文判断

题目解答方法的文字分析

题目要求判断给定的链表是否是回文的，即正向和反向遍历得到的序列是一样的。我们可以使用快慢指针找到链表的中间节点，然后将后半部分链表反转，最后与前半部分比较。如果两部分链表都一样，那么就是回文链表。

例如，对于链表 1 -> 2 -> 3 -> 2 -> 1，找到中间节点 3，将后半部分反转得到 1 -> 2 -> 3 <- 2 <- 1，然后逐个比较节点值即可。

本题解析所用的编程语言

C++

完整且正确的编程代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) {
            return true;  // 空链表或只有一个节点，视为回文
        }
        
        // 使用快慢指针找到中间节点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 反转后半部分链表
        ListNode* prev = nullptr;
        while (slow) {
            ListNode* next = slow->next;
            slow->next = prev;
            prev = slow;
            slow = next;
        }
        
        // 比较前半部分和反转后的后半部分链表
        while (prev) {
            if (head->val != prev->val) {
                return false;  // 值不相等，不是回文
            }
            head = head->next;
            prev = prev->next;
        }
        
        return true;  // 都相等，是回文
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！