题目入口📌:链表的回文结构
问题描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
输入输出案例：
解题分析
本题让我们判断回文就是指，所给的链表是否关于中心对称。
如何确定一个链表回文呢？拿奇数个结点来说，我们可不可以找到尾结点，然后让中心结点之后全部翻转。获取头结点和尾结点，边向中间移动边比较。
以上操作需要分三步来分别实现
- 运用快慢指针的细想来获取中间结点和尾结点。
- 翻转中间结点之后的结点，以尾结点为头。
- 分别设置两个指针指向头、尾结点，然后进行比较。
第一步实现：
获取中间结点，我们可以运用快慢指针的思想。分别设置两个指针分别为fast和slow，slow走一步fast边走两步。
在奇数个节点中，当fast 走到为结点，slow就走到了中间结点了。
偶数个结点比较特殊，我们稍后考虑。
此指针并非C语言中的“指针”，在Java中是一个引用，指向结点。
关于快慢指针的题大家还可以参考这几篇博客：链表的中间结点
ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; }
第二步实现：
我们还以奇数个结点为例，如下图后半个链表，如果我们要逆转链表，那我们还需要在创建两个指针，一个用于改变，一个用于前进。当 cur 为空时结束，因为cur比slow快一步，所以当 cur = null时， slow 也就指向尾结点。
如下，cur 指向的结点next的值改为‘0x333’，如果没有 curNext 的话，cur 就无法前进。
关于逆转详细讲解可以参考这篇：反转链表
ListNode cur = slow.next; while(cur != null){ ListNode curNext = cur.next; cur.next = slow; slow = cur; cur = curNext; }
第三步实现：
经第二步后，slow 已经指向尾结点，所以便可以与头结点进行比较，相同同时向前进一步。
结束的条件是 head == slow
以上是奇数个结点，而偶数个结点，结束的条件是 head.next == slow。如下图
因为偶数没有对称结点值，只有对称轴。当经第一步操作时，slow 只能实现对称轴右一个结点。所以中心轴左右的结点的循序是不可改变的。
而 第三步 slow 和 head 是同时走的，他俩不可能走到同一个结点上，所以便设结束条件为 head.next == slow
while(slow != head && head.next != slow){ if(slow.val == head.val){ slow = slow.next; head = head.next; }else{ return false; } }
代码实现
public class PalindromeList { public boolean chkPalindrome(ListNode head) { // write code here ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } ListNode cur = slow.next; while(cur != null){ ListNode curNext = cur.next; cur.next = slow; slow = cur; cur = curNext; } while(slow != head && head.next != slow){ if(slow.val == head.val){ slow = slow.next; head = head.next; }else{ return false; } } return true; } }
