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

package main


import . "nc_tools"

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
func maxPalindrome(head *ListNode) *ListNode {
	// write code here
	var l int
	linkList := []int{}
	tmpHead := head
	for tmpHead != nil {
		linkList = append(linkList, tmpHead.Val)
		tmpHead = tmpHead.Next
	}
	l = len(linkList)

	//判断是否为回文
	var left, right int
	if l&1 == 1 {
		left = l >> 1
		right = l >> 1
	} else {
		left = l>>1 - 1
		right = l >> 1
	}
	for left >= 0 && right < l && linkList[left] == linkList[right] {
		left--
		right++
	}
	if left == -1 {
		return nil
	}

	//返回最长链表
	lmax := 0
	rmax := 0
	Max := 0
	for i := 0; i < l*2-1; i++ {
		leftIdx := i >> 1
		rightIdx := i%2 + i>>1
		for leftIdx >= 0 && rightIdx < l && linkList[leftIdx] == linkList[rightIdx] {
			leftIdx--
			rightIdx++
		}
		if rightIdx-leftIdx > Max {
			lmax = leftIdx+1
			rmax = rightIdx-1
			Max = (rightIdx - leftIdx-2)
		}
	}
    tmp:=head
    for i:=0;i<rmax;i++{
        tmp=tmp.Next
    }
    tmp.Next=nil
    for i:=0;i<lmax;i++{
        head=head.Next
    }
    return head
}