Palindrome Linked List (0234/Easy)

Given a singly linked list, determine if it is a palindrome. 给出一个单链表，确定它是否是回文。

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

先使用双指针同时遍历head节点，找到中间节点的位置，然后将剩下的部分进行反转，然后比较head和反转后的另一半节点值，如果不相等，则说明它不是回文链表。

此解法的时间复杂度是O(n)，空间复杂度是O(1)。

public boolean isPalindrome3(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    //链表元素奇数个
    if (fast != null) {
        slow = slow.next;
    }

    slow = reverse(slow);
    fast = head;
    while (slow != null) {
        if (fast.val != slow.val) {
            return false;
        }
        fast = fast.next;
        slow = slow.next;
    }
    return true;
}

public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}