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

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) {
        // 将链表节点的值拼接成字符串
        StringBuilder sb = new StringBuilder();
        ListNode cur = head;
        while (cur != null) {
            sb.append(cur.val);
            cur = cur.next;
        }
        String vals = sb.toString();

        int n = vals.length();
        int maxLen = 0; // 最长回文子串的长度
        int maxLeft = 0; // 最长回文子串的左边界
        int maxRight = 0; // 最长回文子串的右边界

        // 遍历字符串，以每个字符为中心，向两边扩展寻找回文子串
        for (int i = 0; i < n * 2 - 1; i++) {
            int left = i / 2;
            int right = (i + 1) / 2;
            while (left >= 0 && right < n && vals.charAt(left) == vals.charAt(right)) {
                // 更新最长回文子串的长度和边界
                if (right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    maxLeft = left;
                    maxRight = right;
                }
                left--;
                right++;
            }
        }

        // 如果最长回文子串的长度等于链表长度，说明整个链表都是回文，返回null
        if (maxLen == n) {
            return null;
        }

        // 找到最长回文子串的起始节点
        cur = head;
        for (int i = 0; i < maxLeft; i++) {
            cur = cur.next;
        }

        ListNode res = cur;

        // 将最长回文子串的后续节点断开
        for (int i = 0; i < maxRight - maxLeft; i++) {
            cur = cur.next;
        }
        cur.next = null;

        return res;
    }
}

知识点：

• 链表操作
• 字符串操作
• 回文串

代码解释大纲：

1. 创建一个StringBuilder对象用于拼接链表节点的值。
2. 遍历链表，将节点的值拼接成字符串。
3. 获取字符串的长度。
4. 初始化最长回文子串的长度、左边界和右边界为0。
5. 遍历字符串，以每个字符为中心向两边扩展，寻找回文子串。
6. 更新最长回文子串的长度和边界。
7. 如果最长回文子串的长度等于链表长度，说明整个链表都是回文，返回null。
8. 根据最长回文子串的边界找到起始节点。
9. 将最长回文子串的后续节点断开。
10. 返回最长回文子串的起始节点。