234. Palindrome Linked List

Given the head of a singly linked list, return true if it is a 
palindrome
 or false otherwise.

 

Example 1:


Input: head = [1,2,2,1]
Output: true
Example 2:


Input: head = [1,2]
Output: false
 

Constraints:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9
 

Follow up: Could you do it in O(n) time and O(1) space?




class Solution {
    public boolean isPalindrome(ListNode head) {
        // 如果链表为空或只有一个元素，直接返回true
        if (head == null || head.next == null) {
            return true;
        }
        // 定义快慢指针，快指针每次移动两步，慢指针每次移动一步
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 反转后半部分链表
        ListNode pre = null, cur = slow, next = slow.next;
        while (cur != null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            if (next != null) {
                next = next.next;
            }
        }
        // 比较前半部分链表和反转后的后半部分链表
        ListNode p1 = head, p2 = pre;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
}