题解 | #牛群编号的回文顺序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) {
        int[] values = new int[getSize(head)];
        ListNode current = head;
        for(int i=0;i<values.length;i++){
            values[i] = current.val;
            current = current.next;
        }
        if(isPalindrome(values)){
            return null;
        }
        int start = 0;
        int end = 0;
        int maxLen = 0;
        for(int i=0;i<values.length;i++){
            for(int j=0;j<values.length;j++){
                if(isPalindrome(values,i,j)&&(j-i)>maxLen){
                    start = i;
                    end = j;
                    maxLen = j-i;
                }
          
            }
        }
        ListNode result = null;
        for(int i=start;i<=end;i++){
            result = addToEnd(result,values[i]);
        }
        return result;
        // write code here
    }
    private static boolean isPalindrome(int[] values){
        int i=0;
        int j=values.length-1;
        while(i<j){
            if(values[i]!=values[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    private static boolean isPalindrome(int[] values,int start, int end){
        while(start<end){
            if(values[start]!=values[end]){
                return false;
            }
            start++;
            end--;
        }
        return true;

    }
    private static int getSize(ListNode head){
        int size = 0;
        ListNode current = head;
        while(current!=null){
            size++;
            current = current.next;
        }
        return size;
    }
    private static ListNode addToEnd(ListNode head,int value){
        ListNode newNode = new ListNode(value);
        if(head==null){
            return newNode;
        }
        ListNode current = head;
        while(current.next!=null){
            current = current.next;
        }
        current.next = newNode;
        return head;
    }
}

1. 将链表的值存储在数组中： 遍历链表，将每个节点的值存储在一个数组中。这样我们就得到了一个可以直接操作的数组，方便后续的处理。
2. 检查数组是否是回文的： 使用两个指针（一个从头开始，一个从尾开始）向中间移动，比较对应位置的值是否相等。如果整个数组是回文的，说明原始链表是回文的，直接返回空链表。
3. 找到最大连续回文子数组： 如果数组不是回文的，我们需要找到最大的连续回文子数组。可以使用两层循环来遍历所有可能的子数组，然后检查每个子数组是否是回文的。记录最大回文子数组的起始索引和结束索引。
4. 根据最大回文子数组构建链表： 使用最大回文子数组的起始索引和结束索引，在原始数组中找到对应的节点值，然后构建一个新的链表。
5. 返回结果： 返回新构建链表的头节点。