57.Palindrome Linked List-回文链表

class Solution {
    public boolean isPalindrome(ListNode head) {
       if(head==null)
            return true;
        //先找到中点
        ListNode s=head;
        ListNode f=head;
        Stack<ListNode> stack=new Stack<>();
        while(f!=null&&f.next!=null){    //快慢指针，当快指针到末尾的时候，慢指针就到了中点
            s=s.next;
            f=f.next.next;
        }
        /*while(s!=null){
            stack.push(s);
            s=s.next;
        }
        while(!stack.isEmpty()){
            if(head.val==stack.pop().val){
                head=head.next;
            }else{
                return false;
            }
        }
        return true;*/
        //中点后面的节点反转
        ListNode q = s.next;
        s.next = null;
        while (q != null) {
            ListNode r = q.next;
            q.next = s;
            s = q;
            q = r;
        }
        //进行匹配
        while (head != null && s != null) {
            if (head.val != s.val) {  //如果有一个匹配不成功，就返回false
                return false;
            }
            head = head.next;
            s = s.next;
        }
        return true;  //当全部都匹配成功的时候，就返回true
    }
}