編寫一個函數(shù)，檢查輸入的鏈表是否是回文的。

示例 1：

輸入： 1->2
輸出： false
示例 2：

輸入： 1->2->2->1
輸出： true

進階：
你能否用 O(n) 時間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

思路： 快慢指針找到一半的點；反轉(zhuǎn)后半部分點，對比是否相同;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 現(xiàn)在slow是一半了;
        ListNode pre = null;
        ListNode temp = slow;
        ListNode tempN = slow;
        while(temp!=null){
            tempN = temp.next;
            temp.next = pre;
            pre = temp;
            temp = tempN;
        }
        ListNode f = head;
        ListNode s = pre;
        while(s!=null){
            if(f.val!=s.val){
                return false;
            }
            f = f.next;
            s = s.next;
        }
        return true;
    }
}