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

思路：将链表从中间反转后，从两头往中间走边走边判断是否回文，且处理奇数个节点的特殊情况即可

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) {
        // write code here
        // 1. 处理特殊情况
        if (head == null || head.next == null) return true;

        // 2. 快慢指针寻找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null ) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 3. 开始从中间节点反转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = slow;
            slow = cur;
            cur = next;
        }

        // 4. 反转后同步从头往后，从尾往前走
        cur = head;
        while (cur != slow) {
            if  (cur.val != slow.val) return false;
            if (cur.next == slow) return true;
            cur = cur.next;
            slow = slow.next;
            
        }

        return true;
    }
}