题解 | #牛群编号的回文顺序#

不使用额外的空间。

大致思路：使用双指针，快指针移动的速度是满指针移动速度的两倍，快指针到达链表的末尾时，慢指针位于链表的中间位置。

此时，反转后半部分的链表，然后依次比较前后两半链表是否相同即可。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return bool布尔型
     */
    public boolean isPalindrome (ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode left = head;
        ListNode right;
        ListNode slow = head;
        ListNode fast = head;
        //如果节点个数是奇数，那么fast最终指向的位置是最后一个节点
        //如果节点个数是偶数，那么fast指向的位置是最后一个节点的前一个元素，此时还需要让fast后移一位
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast.next != null && fast.next.next == null) fast = fast.next;
        }
        //记录下来末尾节点
        //开始反转链表,反转 slow 之后的节点
        right = slow.next;
        ListNode tmp = right.next;
        slow.next = null;
        right.next = slow;
        slow = right;
        right = tmp;
        //循环结束之后，right为null，slow指向最后一个节点，至此后半部分的链表反转完成
        while (right != null) {
            tmp = right.next;
            right.next = slow;
            slow = right;
            right = tmp;
        }
        right = slow;
        //开始比较元素的值
        while (left != null) {
            if (left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }
        return true;
    }
}