回文链表
请判断一个单链表是否为回文链表
输入：1->2->1 输出：true 输入：1->2->2->1 输出：true 输入： 1->2->3 输出：false
注：空链表，单节点链表也为回文链表
考虑空间复杂度O(1),时间复杂度为O(n)
分析思路
基于链表的节点获取，只能通过遍历的形式，基于空间复杂度的情况，肯定是不能申请例如 list、map的数据结构去存储的。
通过大脑的第一反应就是找到中间节点将链表切分为 pre 前段链表、 aft 后段链表两个链表，然后将 pre 链表逆序遍历，aft 链表正序遍历，逐一比对节点值，当发现节点值不相等的时候即输出 false，否则为 true。
那么根据上面的思路，我们的解决思路总结如下：
- 找到中间节点
- pre 逆序遍历， aft 正序遍历
- 节点值比对
找到中间节点
各位想想对于链表数据结构我们如何找到中间节点呢？
快慢双指针，即 fast 指针偏移量为 slow 指针偏移量的两倍，当 fast 指针遍历结束的时候， slow 指针所指的节点不就是中间节点了吗？
这里有个彩蛋需要注意，就是当链表节点总数为奇数和偶数的处理。
示意图：
如何保证 pre 逆序遍历
既然已经找到了 pre 前段链表，逆序遍历不就是对 pre 链表的反转么？ 是的，这里其实就是对链表就行反转。
示意图：
节点值比对
这部分其实就是简单的遍历之后的比对。
归总
通过对问题的拆分，实际上就是讲场景拆分多步骤各个击破，在各个步骤中利用我们掌握的基础知识进行一步步的构建解决问题的步骤。
代码实现
- 构造链表数据结构
public class ListNode{
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
- 判断是否为回文链表代码实现
public class IsPalindrome {
public boolean isPalindRome(ListNode root) {
ListNode fast = root, slow = root, pre=root , prepre=null;
//链表为空链表
if(root == null || root.next == null) return true;
//链表长度为2 边界处理
if(root.next.next == null) {
return root.val == root.next.val ;
}
// 反转单链表
while(fast != null && fast.next != null) {
// 在遍历的时候顺便处理链表反转
fast = fast.next.next;
pre = slow;
slow = slow.next;
pre.next = prepre;
prepre = pre;
}
// 当链表节点数为奇偶数的特殊处理
if(fast != null) slow = slow.next;
// 逐一比对
while ( slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
}