234. 回文链表
请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解析

直接快慢指针，注意奇数位置的判断

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode quick = head;
        ListNode pre = null;
        while(quick!=null && quick.next!=null){
            quick = quick.next.next;
            ListNode next = slow.next;
            slow.next = pre;
            pre = slow;
            slow = next;
        }
        //从1开头，然后一次走两个， x x x x (x) 如果quick此时为空说明偶数，不为空说明奇数
        //这时候slow就是中间位置
        if(quick!=null){
            slow = slow.next;
        }
        while(pre!=null && slow!=null){
            if(pre.val!=slow.val) return false;
            pre = pre.next;
            slow = slow.next;
        }
        return true;

    }
}

注意：本文归作者所有，未经作者允许，不得转载