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

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 ListNode类
     */
    public ListNode maxPalindrome (ListNode head) {
        // write code here
        // 如果整个链表就是一个回文链表，则返回null
        if (isPalindrome(head)) {
            return null;
        }

        List<ListNode> list = new ArrayList<>(); // 用于存储链表的每个节点
        int max = 0; // 记录当前找到的最长回文子链表的长度
        int start = 0, end = 0; // 记录最长回文子链表的起始和结束位置

        // 将链表的每个节点加入到list中
        ListNode cur = head;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }

        // 遍历list，以每个节点为中心向两边扩展查找回文子链表
        for (int i = 0; i < list.size(); ++i) {
            int p1 = i;
            int p2 = i + 1;
            while (p1 >= 0 && p2 < list.size() && (list.get(p1).val == list.get(p2).val)) {
                p1--;
                p2++;
            }
            // 如果找到的回文子链表长度大于当前最大长度，则更新最长回文子链表的位置和长度
            if (p2 - p1 - 1 > max) {
                start = p1 + 1;
                end = p2 - 1;
                max = p2 - p1 - 1;
            }
        }

        // 如果整个链表都是回文链表，则返回null；否则切断最大回文子链表后面的部分并返回最大回文子链表的头节点
        if (start == 0 && end == list.size() - 1) {
            return null;
        } else {
            list.get(end).next = null;
            return list.get(start);
        }
    }

    /**
     * 判断给定链表是否是回文链表
     *
     * @param head 给定链表的头节点
     * @return 若是回文链表则返回true，否则返回false
     */
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>(); // 用于存储链表的值
        ListNode cur = head;
        // 将链表的值加入到list中
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        int i = 0, j = list.size() - 1;
        // 判断list中对应位置的值是否相等，直到i>=j
        while (i < j) {
            if (!list.get(i).equals(list.get(j))) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

该题的主要知识点是链表和回文判断。

代码解释：

1. 检查给定的链表是否是一个回文链表。如果是，直接返回null，因为整个链表都是回文的，无法找到非回文节点。
2. 创建一个ArrayList用于存储链表的每个节点，方便之后的操作。
3. 初始化变量max、start和end，分别用于记录当前找到的最长回文子链表的长度、起始位置和结束位置。
4. 遍历链表，将每个节点加入到ArrayList中。
5. 遍历ArrayList，以每个节点为中心，向左右两边扩展，判断是否形成回文子链表。同时更新最长回文子链表的位置和长度。
6. 如果整个链表都是回文的，则返回null；否则将最长回文子链表的后续部分切断，并返回最长回文子链表的头节点。
7. 编写辅助方法isPalindrome，用于判断给定链表是否是回文链表。该方法使用双指针，分别从链表的头部和尾部向中间遍历，并比较对应位置的值是否相等.