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

1. 会顺序表处理回文串，就能解决

import java.util.*;

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;
        }
        final char[] chars = sb.toString().toCharArray();
        int len = chars.length;
        int max = 1;
        int begin = 0;
        boolean[][] f = new boolean[len+1][len+1];
        for (int j = 1; j < len; ++j) {
            f[j][j] = true;
            for (int i = j - 1; i >= 0; --i) {
                if (chars[i] != chars[j]) {
                    continue;
                }
                f[i][j] = i == j - 1 ? true : f[i + 1][j - 1];
                if (!f[i][j]) {
                    continue;
                }
                final int ll = j - i + 1;
                if (ll > max) {
                    max = ll;
                    begin = i;
                }
            }
        }
        if (begin == 0 && max == len) {
            return null;
        }
        for (int i = 0; i < begin; ++i) {
            head = head.next;
        }
        ListNode tail = head;
        for (int i = 0; i < max - 1; ++i) {
            tail = tail.next;
        }
        tail.next = null;
        return head;
    }
}