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

知识点：

中心扩展法

解题思路：

现将链表的val依次放入String，再使用中心扩展法，找出最长的回文字串，如果回文串长度等于链表长度，直接返回nil，反之返回对应回文链表。

中心扩展法：顾名思义就是找到中心点，向两边依次扩展，一边扩展一边判断是否相等。主要难度在于找到正确的中心点，其实随便列举一些例子就能找到规律如“aba”，中心点就有a,b,a,ab,ba五个，也就是n*2-1个，点具体对应位置是left = i/2，right =（i+1)/2

package main

import "strconv"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
func maxPalindrome(head *ListNode) *ListNode {
	// write code here
	vals := ""
	cur := head
	for cur != nil {
		vals +=strconv.Itoa(cur.Val)
        cur = cur.Next
	}
	n := len(vals)
	maxLen := 0
	maxLeft := 0
    maxRight:=0
	for i := 0; i < n*2-1; i++ {
		left := i / 2
		right := (i + 1) / 2
		for left >= 0 && right < n && vals[left] == vals[right] {
			if right-left+1 > maxLen {
				maxLen = right - left + 1
				maxLeft = left
                maxRight = right
			}
			left--
			right++
		}
	}
	if maxLen == n {
		return nil
	}
	cur = head
	for i := 0; i < maxLeft; i++ {
		cur = cur.Next
	}
    res:=cur
    for i:=0 ;i<maxRight - maxLeft;i++{
         cur = cur.Next
    }
    cur.Next = nil
	return res
}