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

该题主要考察的知识点如下：（该代码考察，题解很多种，这里列举我写的这种）

1. 单链表的基本操作：包括遍历链表、获取链表长度、访问链表节点等。
2. 快慢指针：使用快慢指针可以找到链表的中间节点，这是判断回文链表的一种常见方法。
3. 反转链表：通过反转链表可以得到链表的逆序链表，便于与原链表进行比较。

这里定义了一个 isPalindrome 方法，用于判断链表的编号顺序是否是回文的。具体步骤如下：

1. 首先判断边界情况，如果链表为空或者只有一个节点，视为回文，直接返回 true。
2. 使用快慢指针找到链表的中间节点。
3. 反转链表的后半部分，得到反转后的链表。
4. 比较前半部分链表和反转后的后半部分链表的节点值，如果存在不相等的节点，返回 false，否则返回 true。

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 reversedHalf = reverseList(middle.next);

        // 比较前半部分链表和反转后的后半部分链表
        ListNode p1 = head;
        ListNode p2 = reversedHalf;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.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 reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}