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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
#include <stdio.h>
void getNums(struct ListNode* head, int* res, int* length) {
    while (head) {
        res[(*length)++] = head->val;
        head = head->next;
    }
}
bool ishuiwen(int* nums, int start, int end) {
    while (start < end) {
        if (nums[start] != nums[end]) {
            return false;
        } else {
            start++;
            end--;
        }
    }
    return true;
}
struct ListNode* maxPalindrome(struct ListNode* head ) {
    int* res = malloc(sizeof(int) * 100000);
    int length = 0;
    getNums(head, res, &length);
    if (ishuiwen(res, 0, length - 1)) {
        return NULL;
    } else {
        int start = 0, end = 0;
        int max = -1;
        for (int i = 1; i < length - 1; i++) {
            int left = i - 1, right = i + 1;
            while (left >= 0 && right < length && res[left] == res[right]) {
                left--;
                right++;
            }
            if (left == i - 1 && right == i + 1) {
                if (res[left] == res[i]) {
                    start = left;
                    end = i;
                }
                if (res[right] == res[i]) {
                    start = i;
                    end = right;
                }
            } else {
                left++;
                right--;
                if (right - left + 1 > max) {
                    max = right - left + 1;
                    start = left;
                    end = right;
                }
            }
        }
        for (int i = 0; i < length - 1; i++) {
            if (res[i] == res[i + 1]) {
                int start1 = i, end1 = i + 1;
                while (start1 >= 0 && end1 < length && res[start1] == res[end1]) {
                    start1--;
                    end1++;
                }
                start1++;
                end1--;
                if (end1 - start1 + 1 > max) {
                    max = end1 - start1 + 1;
                    start = start1;
                    end = end1;
                }
            }
        }
        struct ListNode* node = malloc(sizeof(struct ListNode));
        struct ListNode* num = node;
        node->next = NULL;
        for (int i = start; i <= end; i++) {
            struct ListNode* temp = malloc(sizeof(struct ListNode));
            temp->val = res[i];
            temp->next = NULL;
            node->next = temp;
            node = temp;
        }
        return num->next;
    }
}

注意从回文字符串长度的奇偶性来分别讨论