XingHuiSama の博客

给你一个单链表的头节点 head ，请你判断该链表是否为。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

1. 算法核心思想：双指针与状态复用

判断单向链表是否为回文结构的传统做法是将其遍历并存入数组，但这会产生额外的空间开销。为了实现 O(1) 的空间复杂度，必须在原链表上进行操作。

核心在于对慢指针的复用。在利用快慢指针寻找链表中点的同时，让慢指针“边走边拆桥”，将其走过的前半段链表直接反转。这样，当快指针到达链表末尾时，整个链表已经被从中间一分为二，且前半段的指针方向已完全逆转，可以直接与后半段进行同步遍历比对。

2. 逻辑拆解

寻找中点与同步反转：设立 fast 每次步进两个节点，slow 每次步进一个节点。在 slow 步进的过程中，利用 temp 和 pre 变量将其当前节点指向前一个节点。循环的终止条件 fast != NULL && fast->next != NULL 控制了快指针的安全边界。
奇偶长度的精准定位：当外层 while 循环终止时：
- 若链表长度为偶数：fast 刚好越界变为 NULL，此时 slow 准确停在后半段的第一个节点。
- 若链表长度为奇数：fast 停在最后一个节点（非 NULL），此时 slow 停在整个链表的最中间节点。由于回文结构的中心节点不需要进行比对，因此执行 slow = slow->next 将其跳过。
比对阶段：经过上述操作，pre 指针变为了前半段（已反转）的头节点，slow 指针变为了后半段的头节点。此时只需用一个常规的 while 循环依次比对两者的 val 即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {

        if (head == NULL || head->next == NULL) {
            return true;
        }
        //快慢指针
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = NULL;

        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;

            ListNode* temp = slow->next;
            slow->next = pre;
            pre = slow;
            slow = temp;
        }

        if (fast != NULL) {
            slow = slow->next;
        }

        while (slow != NULL) {
            if (pre->val != slow->val) {
                return false;
            }
            pre = pre->next;
            slow = slow->next;
        }

        return true;
    }
};

3. 复杂度分析

时间复杂度：O(N)。（N 为链表的节点总数）。快慢指针寻找中点并反转前半段的过程耗时约 N/2 次操作；后续的比对过程耗时约 N/2 次操作。整体操作次数与节点数呈线性关系。
空间复杂度：O(1)。算法仅声明了 slow、fast、pre、temp 几个固定数量的指针变量，未申请任何与数据规模相关的额外空间。