思路：先用快慢指针找到中间点，然后把后半部分翻转，然后同时遍历前半部分和后半部分，都一样就是回文链表。
class Solution {
public boolean isPalindrome(ListNode head) {
//边界条件 1.如果没有数或者只有一个数
if(head == null || head.next == null) return true;//只有一个节点是head.next == null
//如果只有两个数，判断它们的值是否一样
if(head.next.next == null) return head.val == head.next.val;
//建立一个快指针
ListNode fast = head;
//建立一个慢指针
ListNode slow = head;
//如上图蓝色部分，如果链表的个数是奇数fast.next = null就结束
//如果链表的个数是偶数，fast.next.next = null就遍历结束
while(fast.next != null && fast.next.next != null){
//slow走一步
slow = slow.next;
//fast走两步
fast = fast.next.next;
}
//反转，反转后newRightHead是右边部分的头节点，slow指向的是中间节点，所以反转部分的头节点是slow.next
ListNode newRightHead = resverse(slow.next);
//左边部分的头节点
ListNode newLeftHead = head;
//slow是中间节点，如上图当链表的长度为奇数的时候，右边部分会短一些，用右边部分来判断
while(newRightHead != null ){
//左右两个部分同时移动，如果遇到值不相等的就返回false
if(newLeftHead.val != newRightHead.val){ //值不相等
return false;
}
//继续移动
newRightHead = newRightHead.next;
//继续移动
newLeftHead = newLeftHead.next;
}
//都判断完了肯定返回true呀
return true;
}
private ListNode resverse(ListNode head){
if(head == null || head.next == null) return head;
ListNode newHead = resverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
反转链表部分的解析
