234. Palindrome Linked List

和检查回文数组的想法类似，因为是单链表，当我们需要从尾部访问前面时，需要翻转链表。翻转的范围应该是从中间到尾部。
这里有两种方法找到中间元素，一种是先遍历求得长度N，再二次遍历达到中间的位置，还有一种是使用快慢指针，当快指针到达末尾时，慢指针就是我们想要的位置。
对于奇数和偶数类型，我们都可以从N/2+1的位置开始反转。对于偶数来说，正好是后半部分的下一个开始，对于奇数部分来说，正好是正中间，我们可以在比较过程无视这个结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
       if(head==null||head.next==null) return true;
       ListNode fast = head.next.next;
        ListNode slow = head.next;
        // search for the mid
        while(fast!=null)
        {
            fast=fast.next==null?null:fast.next.next;
            slow=slow.next;
        }
        ListNode p1 =slow;
        ListNode p2= slow.next;
        p1.next=null;
        while(p2!=null)
        {
            ListNode temp = p2.next;
            p2.next=p1;
            p1=p2;
            p2=temp;
        }
        p2=head;
        while(p1!=null&&p2!=null)
        {
            if(p1.val!=p2.val)
                return false;
            p1=p1.next;
            p2=p2.next;
        }
        return true;
        
    }
}