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

题目考察的知识点是：

本题主要考察的是链表知识，是否回文，获取头部。

题目解答方法的文字分析：

可以使用中心扩展法，即遍历整个链表，将链表中的每一个节点看作中点，使用left和right指针分别向左和向右遍历牛群编号，判断其是否满足回文串的要求，并找到最长的回文串。使用该方法时，要考虑到奇数回文串和偶数回文串的情况，两种情况下的回文串取最长的一个。

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

java语言。

完整且正确的编程代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode maxPalindrome (ListNode head) {
        // write code here
        left = head;
        if (isPalindrome(head)) return null;
        StringBuilder sb = new StringBuilder();
        ListNode p = head;
        while (p != null) {
            sb.append(p.val);
            p = p.next;
        }
        String str = sb.toString();
        int start = 0, end = 0;
        for (int i = 0; i < str.length() - 1; i++) {
            int [] res1 = palindrome(str, i, i);
            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 != null) {
            if (start == 0) {
                startNode = head;
                break;
            } else {
                head = head.next;
                start --;
            }
        }
        while (head != null) {
            if (end == 0) {
                System.out.println(head.val);
                break;
            } else {
                head = head.next;
                end --;
            }

        }
        head.next = null;
        return startNode;
    }

    ListNode left = null;
    public boolean isPalindrome(ListNode right) {
        if (right == null)
            return true;
        boolean result = isPalindrome(right.next);
        result = result & (left.val == right.val) ;
        left = left.next;
        return result;
    }

    public int[] palindrome(String str, int i, int j) {
        while (i >= 0 && j < str.length()) {
            if (str.charAt(i) == str.charAt(j)) {
                --i;
                ++j;
            } else break;
        }
        return new int[] {i, j};
    }
}