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

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 slow = head; 
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 反转后半段链表
	    // slow 最终指向中间节点
        ListNode temp = reverse(slow);
	    // head:1->2->3->2->1  temp:1->2  slow:3
	    // head:1->2->3->1  temp:1->3  slow:3
        while (head != slow && temp != null) {
            if (head.val != temp.val) {
                return false;
            }
            head = head.next;
            temp = temp.next;
        }
        return true;
    }
  
	 /**
     * 反转链表
     * @param head
     * @return
     */
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

本题的关键在于找到链表的中间节点，可以用快慢指针来遍历链表，最终慢指针会指向中间节点，反转后半段的链表即可进行回文判断