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

• 题目考察的知识点 : 回文理解，中心扩散法
• 题目解答方法的文字分析：

1. 遍历链表保存所有节点的值到字符串vals中
2. 从字符串vals中查找最大回文子串的长度和位置
3. 根据最大回文子串的开始和结束位置,在链表中定位对应的节点
4. 设置对应的节点next指针,断开最大回文子链表
5. 如果整个链表就是回文,返回None

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
    def maxPalindrome(self, head: ListNode) -> ListNode:
        vals = ""
        cur = head 
        while cur:
            vals += str(cur.val)
            cur = cur.next

        n = len(vals)
        maxLen = 0
        maxLeft = 0
        maxRight = 0

        for i in range(2*n-1):
            left = i // 2
            right = (i + 1) // 2
        
            while left >= 0 and right < n and vals[left] == vals[right]:
                if right - left + 1 > maxLen:
                    maxLen = right - left + 1
                    maxLeft = left
                    maxRight = right
                left -= 1
                right += 1
            
        if maxLen == n:
            return None
    
        cur = head
        for i in range(maxLeft):
            cur = cur.next
        res = cur
    
        for i in range(maxRight - maxLeft):
            cur = cur.next
        cur.next = None
    
        return res