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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

链表，回文判断，字符串操作，双指针

题目解答方法的文字分析

这个题目需要解决两个主要任务：首先，判断整个链表是否为回文；其次，如果不是回文，要找到最大连续回文子链表。解决思路如下：

1. 首先，我们实现一个名为 isPalindrome 的函数，用于判断给定链表是否为回文。为了做到这一点，我们使用递归的方法，并同时维护一个左指针 left 和从链表头部开始逐步移动的右指针 right。在递归过程中，我们不断比较 left 和 right 指向的节点的值，如果有值不相等的情况，则返回 false，否则返回 true。
2. 如果整个链表不是回文，我们可以将链表中每个节点的值连接成一个字符串，然后从每个节点开始，向前和向后扩展，判断是否构成回文。我们维护两个指针 i 和 j，从每个节点开始扩展，如果 str[i] 和 str[j] 相等，则向两侧扩展。在这个过程中，我们记录扩展的范围，然后找到最大回文子链表的起始和结束位置。
3. 最后，根据最大回文子链表的起始和结束位置，截取链表以获取最大回文子链表，并返回其头节点。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    ListNode* maxPalindrome(ListNode* head) {
        left = head;
        // 如果整个链表是回文，返回空链表
        if (isPalindrome(head)) return nullptr;
        
        // 将链表中每个节点的值拼接成字符串
        string str = "";
        ListNode* p = head;
        while (p != nullptr) {
            str += to_string(p->val);
            p = p->next;
        }
        
        int start = 0, end = 0;
        for (int i = 0; i < str.length() - 1; i++) {
            // 向两侧扩展，得到回文的范围
            vector<int> res1 = palindrome(str, i, i);
            vector<int> res2 = palindrome(str, i, i + 1);
            if (res1[1] - res1[0] > end - start) {
                start = res1[0];
                end = res1[1];
            }
            if (res2[1] - res2[0] > end - start) {
                start = res2[0];
                end = res2[1];
            }
        }
        start++;
        end--;
        
        // 找到最大回文子链表的起始节点
        ListNode* startNode = head;
        end = end - start;
        while (head != nullptr) {
            if (start == 0) {
                startNode = head;
                break;
            } else {
                head = head->next;
                start--;
            }
        }
        
        // 找到最大回文子链表的结束节点
        while (head != nullptr) {
            if (end == 0) {
                break;
            } else {
                head = head->next;
                end--;
            }
        }
        
        // 断开链表，只保留最大回文子链表
        if (head != nullptr) {
            head->next = nullptr;
        }
        
        return startNode;
    }

    ListNode* left = nullptr;
    // 判断回文的递归函数
    bool isPalindrome(ListNode* right) {
        if (right == nullptr)
            return true;
        bool result = isPalindrome(right->next);
        result = result && (left->val == right->val);
        left = left->next;
        return result;
    }

    // 向两侧扩展，判断回文的函数
    vector<int> palindrome(string str, int i, int j) {
        while (i >= 0 && j < str.length()) {
            if (str[i] == str[j]) {
                --i;
                ++j;
            } else break;
        }
        return vector<int>{i, j};
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！