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

考察的知识点：回文链表的处理；

解答方法分析：

1. 首先定义了一个私有成员函数 aroundCenter，用于找到以某个索引为中心的最长回文串的起始索引、结束索引和长度。
2. 在 maxPalindrome 函数中，首先判断给定的链表是否为空，如果为空，则直接返回。
3. 遍历链表，将节点的值存储在数组 arr 中。
4. 使用双指针法判断数组 arr 是否是回文的，即从数组的两端向中间遍历，如果对应位置的元素值不相等，则将 isPalindrome 置为 false。
5. 如果整个链表是回文的，则直接返回 nullptr。
6. 定义变量 count、left 和 right，用于记录最大回文子串的长度以及其起始索引和结束索引。
7. 遍历数组 arr，从索引 1 开始，分别以当前位置为中心，向两侧扩展检查回文串的长度，并更新 count、left 和 right。
8. 将指针 cur 移动到链表头部，并设置变量 leftBound 为 0。
9. 通过移动指针 cur 和增加 leftBound，将指针 cur 移动到最长回文子串的起始位置处。
10. 定义节点指针 result，将其指向 cur。
11. 将指针 cur 按照 left 和 right 的值进行移动，直到 left 和 right 相等。
12. 将指针 cur 的下一个节点设置为 nullptr，表示最长回文子串的结束。
13. 返回节点指针 result，即最长回文子串的头节点。

所用编程语言：C++；

完整编程代码：↓

#include <vector>
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

class Solution {
  public:

    std::vector<int> aroundCenter(std::vector<int>& arr, int i, int j) {
        while (i >= 0 && j < arr.size() && arr[i] == arr[j]) {
            i--;
            j++;
        }
        return { i + 1, j - 1, j - i - 1 };
    }

    ListNode* maxPalindrome(ListNode* head) {
        if (!head) return head;

        ListNode* cur = head;
        std::vector<int> arr;
        while (cur) {
            arr.push_back(cur->val);
            cur = cur->next;
        }

        int left = 0;
        int right = arr.size() - 1;
        bool isPalindrome = true;
        while (left <= right) {
            if (arr[left] != arr[right]) {
                isPalindrome = false;
                break;
            }
            left++;
            right--;
        }
        if (isPalindrome) return nullptr;

        int count = 0;
        left = 0;
        right = 0;

        for (int i = 1; i < arr.size(); i++) {
            std::vector<int> res1 = aroundCenter(arr, i, i); // 奇数情况
            std::vector<int> res2 = aroundCenter(arr, i - 1, i); // 偶数情况
            int curlen1 = res1[2];
            int curlen2 = res2[2];
            int max = std::max(curlen1, curlen2);

            if (count < max) {
                count = max;
                left = max == curlen1 ? res1[0] : res2[0];
                right = max == curlen1 ? res1[1] : res2[1];
            }
        }

        cur = head;
        int leftBound = 0;
        while (leftBound < left) {
            cur = cur->next;
            leftBound++;
        }

        ListNode* result = cur;
        while (left < right) {
            cur = cur->next;
            left++;
        }

        cur->next = nullptr;
        return result;
    }

};