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

基本思路是将链表转换为字符串，并使用动态规划的方法来寻找最长回文子链表。

首先，判断链表是否为空或只有一个节点，如果是的话，则直接返回null。

然后，将链表中的节点值依次添加到StringBuilder中，以形成一个字符串表示整个链表。

接下来，初始化一些变量，包括长度（len）为字符串长度、最大回文子链表长度（maxLen）初始化为1，和回文子链表起始位置（begin）初始化为0。

接着，创建一个布尔型的二维数组dp，其中dp[i][j]表示字符串s的第i个字符到第j个字符是否为回文串。将所有长度为1的子串都初始化为回文串。

将字符串转换为字符数组charArray，为后续判断字符是否相等做准备。

开始进行动态规划的递推过程。

首先，外层循环枚举子串长度（l从2到len）。

然后，内层循环枚举左边界（i从0到len）。

确定右边界（j = i + l - 1），并检查是否越界，若越界则退出内层循环。

如果charArray[i]与charArray[j]不相等，则dp[i][j]为false；否则，如果子串长度小于等于3，则直接为回文串，即dp[i][j]为true；如果子串长度大于3，则需要根据内圈dp[i+1][j-1]的值来判断是否为回文串。

如果dp[i][j]为true，并且子串长度大于maxLen，则更新maxLen和begin。

最后，根据begin和maxLen找到链表中的最大回文子链表的起始节点和结束节点（tail），然后将结束节点的next指针置为null，以断开后续节点。

最后，返回最大回文子链表的起始节点。

需要注意的是，如果整个链表都是回文的，即begin为0且maxLen等于sb.length()，则返回null。

public class Solution {

    public ListNode maxPalindrome (ListNode head) {
        if (head == null || head.next == null) return null;

        StringBuilder sb = new StringBuilder();
        ListNode cur = head;
        while (cur != null) {
            sb.append(cur.val);
            cur = cur.next;
        }
        // 求这个最大的连续回文子链表
        int len = sb.toString().length();
        int maxLen = 1;
        int begin = 0;
        // dp[i][j]表示s[i,j]是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为1的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        char[] charArray = sb.toString().toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int l = 2; l <= len; l++) {
            // 枚举左边界
            for (int i = 0; i < len; i++) {
                // 有子串长度+左边界 -> 右边界： i+l-1
                int j = i + l - 1;
                // 如果右边界越界，结束内层循环
                if (j >= len) break;

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) dp[i][j] = true; //长度为2 3直接是
                    else dp[i][j] = dp[i + 1][j - 1]; // 等于内圈是否满足
                }
                // 只要dp[i][j]==true 就表示字串s[i,j]是回文子串,记录此时回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }

        if (begin == 0 && maxLen == sb.length()) return null; //整个串都是回文的

        while (begin-- > 0) {
            head = head.next;
        }
        ListNode tail = head;
        for (int p = 0; p < maxLen - 1; p++) {
            tail = tail.next;
        }
        tail.next = null; // 断掉后面
        return head;
    }
}