题解 | #牛群编号的回文顺序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) {
        // write code here
  ListNode dummy = new ListNode(-1);
        ListNode change = dummy;
        ListNode cur = head;
        int size = 0;
        int idx = 0;
        while (cur != null) {
            cur = cur.next;
            ++size;
        }
        List<Integer> vec = new ArrayList<>(size);
        cur = head;
        while (cur != null) {
            vec.add(idx, cur.val);
            cur = cur.next;
            ++idx;
        }

        int start = 0;
        int end = vec.size() - 1;

        boolean flag = false;
        while (start <= end) {
            if (vec.get(start) != vec.get(end)) {
                flag = false;
                break;
            } else {
                start++;
                end--;
                flag = true;
            }
        }
        if (flag) {
            return null;
        }
        cur = head;
        start = 0;
        end = 0;
        for (int i = 0; i < vec.size(); ++i) {
            int[] index1 = findIndex(vec, i, i);
            int[] index2 = findIndex(vec, i, i + 1);
            if (index1[1] - index1[0] > end - start) {
                start = index1[0];
                end = index1[1];
            }
            if (index2[1] - index2[0] > end - start) {
                start = index2[0];
                end = index2[1];
            }
        }

        for (int i = 0; i < start; ++i) {
            cur = cur.next;
        }

        size = end - start + 1;
        while (size > 0) {
            change.next = cur;
            cur = cur.next;
            change = change.next;
            change.next = null;
            size--;
        }
        return dummy.next;
    }

    private int[] findIndex(List<Integer> vec, int left, int right) {
        while (left >= 0 && right < vec.size() && vec.get(left).equals(vec.get(right))) {
            --left;
            ++right;
        }
        return new int[]{left + 1, right - 1};
    }
}

这道题主要考察的是链表的遍历和操作，以及回文字符串的判断和查找。

代码的解释大纲：

• 定义了一个名为ListNode的内部类，表示链表节点，包含一个整数值val和指向下一个节点的引用next。
• maxPalindrome方法接收一个链表头节点head作为参数，并返回一个新链表的头节点。
• 创建一个虚拟头节点dummy和一个变量change用于构建新链表，初始化为-1。
• 遍历原链表，计算链表的长度size。
• 创建一个大小为size的数组列表vec，用于存储链表节点的值。
• 再次遍历原链表，将节点的值保存在vec中。
• 初始化两个指针start和end分别指向vec的开头和结尾。
• 判断是否存在回文字符串，即判断vec[start]和vec[end]是否相等，若不相等则不可能存在回文字符串。
• 如果存在回文字符串，返回null。
• 重新将cur指针指向原链表的头节点。
• 使用双指针技术，在vec中遍历每个位置作为回文字符串的中心，分别找到奇数长度和偶数长度回文字符串的起始和结束位置。
• 根据找到的最长回文字符串的起始和结束位置start和end，遍历原链表，将对应节点添加到新链表中。
• 返回虚拟头节点的下一个节点作为新链表的头节点。
• 定义了一个辅助方法findIndex，接收一个数组列表vec和两个边界值left和right，返回一个包含左右索引值的整型数组，用于查找回文字符串的起始和结束位置。