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

题目考察的知识点：与链表有关的题基本都是插入，删除，交换顺序等，解决这些问题通常将链表的指针进行修改。

问题分析：判断一个单链表是否是回文链表，如果是，则返回空；如果不是，则返回链表的最大回文子链表。这里投机取巧一下，将链表输入到一个数组中，再找这个数组中最大的回文子序列。

本题解析所用的编程语言：c++

bool isPalindrome(ListNode* head)
{
    // write code here
    vector<int> v;
    while (head)
    {
        v.push_back(head->val);
        head = head->next;
    }
    for (int i = 0, j = v.size() - 1; i < j; ++i, --j)
    {
        if (v[i] != v[j])
        {
            return false;
        }
    }

    return true;
}
ListNode* maxPalindrome(ListNode* head)
{
    // write code here
    if (isPalindrome(head)) //如果是回文，返回nullptr
        return nullptr;

    vector<ListNode*> v; //将链表搞到一个数组里，在这个数组中找最大子链长
    int max = 0;
    int p1 = 0, p2 = 0;
    int start = 0, end = 0;

    while (head)
    {
        v.push_back(head);
        head = head->next;
    }

    for (int i = 0; i < v.size(); ++i)
    {
        p1 = i;
        p2 = i + 1;
        while ((p1 >= 0 && p2 + 1 < v.size()) && (v[p1]->val == v[p2]->val || v[p1]->val == v[p2 + 1]->val)) //回文的个数可能是奇数，所以不但要比较相邻两个数，还要比较相隔一个数的两个数
        {
            if (v[p1]->val == v[p2 + 1]->val && p2 - p1 == 2) //回文的个数是奇数，++p2
                ++p2;
            --p1;   
            ++p2;
        }
        if (p2 - p1 > max) //将最大的子序列进行标记
        {
            start = p1;
            end = p2;
            max = p2 - p1;
        }
    }
    v[end]->next = nullptr;

    return v[start];
}