✨hello，进来的小伙伴们，你们好耶！✨
🍖🍖系列专栏：【牛客刷题】
🍈🍈作者简介：一名双非本科大三在读的Java编程小白，启夜星辰，你我同行！
🥟🥟给大家推荐一个超级好用的刷题网站——牛客网！
问题描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
解题思路
思路： 1.首选判断链表是否为空。
2.找中点：设置两个引用fast、slow从头开始走，fast每次走两个节点，slow每次走一个节点，当fast走到链表尾，slow正好走到链表中点。
3.翻转后段链表：设置一个cur引用，让他置于中点的下一个节点cur=slow.next，从cur开始将节点指向逆向翻转，每次翻转完成slow向后走一步slow=cur，让slow走到尾部。
4.分别从链表头尾两端开始比较，如果遇到val值不一样的情况，则不是回文，否则是回文。
5.注意这里我们需要判断偶数的情况，当我们的A.next == slow的时候那么就意味着前后已经遍历完成了，二者即将相遇，如果我们不加判断的话，那么A.next就会继续向下一个节点走，我们的slow也会往后走去，那么两者永远不能相遇，程序就出问题了。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
if (A == null) {//没有节点
return false;
}
if (A.next == null) { //只有一个节点 一定是回文结构
return true;
}
//找到中点
ListNode fast = A;
ListNode slow = A;
ListNode cur = A;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//翻转
cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//比较
while (A != slow) {
if (A.val != slow.val) {//有一个不相等说明不是回文结构
return false;
}
if (A.next == slow) {
/*偶数情况下 A.next等于slow说明二者都遍历完成了,即将相遇,
那么证明这个结构已经是回文结构了
如果不加判断那么A继续next,slow继续next会往后走，就会判断错误！*/
return true;
}
A = A.next;
slow = slow.next;
}
return true;
}
}
运行结果：
