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

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
        if (head == null || head.next == null) {
            return true; // 链表为空或只有一个节点，视为回文链表
        }

        ListNode middle = findMiddle(head);
        ListNode secondHalfReversed = reverseLinkedList(middle.next);
        ListNode firstHalf = head;
        ListNode secondHalf = secondHalfReversed;

        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false; // 值不相等，不是回文链表
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true; // 所有值都相等，是回文链表
    }

    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    private ListNode reverseLinkedList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        return prev;
    }
}

题目考察的知识点是：

判断链表是否为回文链表。

解题方法分析：

1. 判断链表是否为回文链表可以使用双指针和反转链表的思想。首先，使用快慢指针找到链表的中间节点。
2. 在找到中间节点的过程中，可以将前半部分链表进行反转。
3. 接下来，比较前半部分反转后的链表和后半部分链表的值是否相同，如果全部相同，则链表为回文链表。