判断一个链表是否为回文结构（C++）

问题描述

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

数据范围： 链表节点数 0≤n≤1050≤n≤105，链表中每个节点的值满足 ∣val∣≤107∣val∣≤107

示例1

输入：

{1}

返回值：

true

示例2

输入：

{2,1}

返回值：

false

说明：

2->1     

示例3

输入：

{1,2,2,1}

返回值：

true

说明：

1->2->2->1     

解题思路

        通过快慢指针找到链表的中点，并将后半部分链表进行反转。首先，利用快慢指针法确定链表的中点，接着反转后半部分链表。然后，分别比较链表的前半部分和反转后的后半部分是否相等，如果有任何不匹配，返回 false，否则返回 true。这样可以有效判断链表是否为回文链表。

代码实现

    bool isPail(ListNode* head) {
        // write code here
        if(head == nullptr|| head->next == nullptr) return true;
        ListNode* slow, *fast;
        slow = fast = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        if(fast != nullptr) slow = slow->next;
        ListNode* cur, *temp, *pre;
        cur = pre = slow;
        temp = cur->next;
        pre->next = nullptr;
        while(temp != nullptr)
        {
            cur = temp;
            temp = temp->next;
            cur->next = pre;
            pre = cur;
        }
        while(cur != nullptr)
        {
            if(cur->val != head->val) return false;
            cur = cur->next;
            head = head->next;
        }
        return true;
    }

代码解析

1. 初始话和边界条件检查

如果链表为空或只有一个元素，直接返回 true，因为空链表或单个元素的链表本身就是回文。

if (head == nullptr || head->next == nullptr) return true;

2. 快慢指针定位链表中点

使用快慢指针法，slow 每次移动一步，fast 每次移动两步。最终，slow 会停在链表的中间位置。当 fast 走到链表末尾时，slow 指向的节点就是链表的中点。

ListNode* slow, *fast;
slow = fast = head;
while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
}

3. 处理奇数长度链表

如果 fast 不为空，说明链表长度为奇数，slow 会指向中间节点。为了比较左右两部分，slow 向后移动一步，指向后半部分链表的起始节点。

if (fast != nullptr) slow = slow->next;

4. 反转后半部分链表

从中点 slow 开始，将后半部分链表反转。使用三个指针：cur 指向当前节点，pre 指向前一个节点，temp 用来保存下一个节点。逐步将每个节点的 next 指向前一个节点，直到整个后半部分链表被反转。

ListNode* cur, *temp, *pre;
cur = pre = slow;
temp = cur->next;
pre->next = nullptr;
while (temp != nullptr) {
    cur = temp;
    temp = temp->next;
    cur->next = pre;
    pre = cur;
}

5. 比较前后两部分链表

依次比较前半部分链表（从 head 开始）和反转后的后半部分链表（从 cur 开始）。如果有任何不相等的值，说明链表不是回文，返回 false。如果两者完全匹配，返回 true。

while (cur != nullptr) {
    if (cur->val != head->val) return false;
    cur = cur->next;
    head = head->next;
}

总结

        代码通过快慢指针找到链表的中点，并反转后半部分链表，最后比较前后两部分是否一致，以此判断链表是否是回文链表。