问题描述
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 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 hereif(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;
}
总结
代码通过快慢指针找到链表的中点，并反转后半部分链表，最后比较前后两部分是否一致，以此判断链表是否是回文链表。