LeetCode234. 回文链表

题目链接：LeetCode234

 如何用O(1)的空间复杂度才是难点，首先定义两个指针，一个快指针high，一个慢指针low，快指针每次走两个节点，慢指针每次走一个，这样当快指针指向最后一个节点的时候，慢指针指向了中点，然后再定义一个tmp指针，首先将将中点的next指向null，然后将中点以后的链表指针全部翻转，都做完了以后从第一个节点和最后一个节点同时出发进行遍历，如果中途有值不一样就直接返回false，终止条件是这两个指针不等于null，因为指向中点的下一个节点就是null

/**
 * 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)
            return true;
        ListNode low = head;//快指针，每次走两个节点
        ListNode high = head;//慢指针，每次走一个节点
        while(high.next != null && high.next.next != null) {
            low = low.next;//find mid
            high = high.next.next;//find end
        }
        high = low.next;
        low.next = null;
        ListNode tmp = null;
        while(high != null) {//swap 
            tmp = high.next;
            high.next = low;
            low = high;
            high = tmp;
        }
        tmp = low;
        high = head;
        boolean res = true;
        while(low != null && high != null) {
            if(low.val != high.val) {
                res = false;
                break;
            }
            high = high.next;
            low = low.next;
        }
        return res;
    }
}