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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <ios>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */

    bool huiwen(vector<int> temp)
    {
        int left = 0;
        int right = temp.size()-1;

        while(left<right)
        {
            if(temp[left]!=temp[right])
                return false;
            ++left;
            --right;
        }

        return true;
    }

    ListNode* maxPalindrome(ListNode* head) {
        // write code here
        vector<int> v;

        ListNode* t = head;

        while(t)
        {
            v.emplace_back(t->val);
            t = t->next;
        }

        // 如果整个链表顺序都是回文的，则返回空链表
        if(huiwen(v))
            return nullptr;

        vector<int> ans;
        // 双重遍历找出最长连续回文子串
        for(int left=0; left<v.size();++left)
        {
            for(int right=left+1; right<v.size(); ++right)
            {
                vector<int> temp(v.begin()+left,v.begin()+right+1);
                if(huiwen(temp))
                {
                    if(ans.size() < temp.size())
                        ans = temp;
                }
            }
        }

        ListNode* res = new ListNode(-1);
        t = res;
        for(int i=0; i<ans.size(); ++i)
        {
            t->next = new ListNode(ans[i]);
            t = t->next;
        }

        return res->next;
    }
};