题解 | #链表判断回文#

思路： 1.万年不变判断链表是否为空（纯属个人习惯）

2.找中点：设置两个引用fast、slow从头开始走，fast每次走两个节点，slow每次走一个节点，当fast走到链表尾，slow正好走到链表中点。

3.翻转后段链表：设置一个cur引用，让他置于中点的下一个节点cur=slow.next，从cur开始将节点指向逆向翻转，每次翻转完成slow向后走一步slow=cur，让slow走到尾部。

4.分别从链表头尾两端开始比较，如果遇到val值不一样的情况，则不是回文，否则是回文。

ps：注意链表节点数为奇数和偶数的情况。

/*
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 true;
        }
        // write code here
        //找到中点
        ListNode fast=A;
        ListNode slow=fast;
        ListNode cur=fast;
        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){
                return true;
            }
            A=A.next;
            slow=slow.next;
        }
        return true;
    }
}