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

• 题目考察的知识点： 考察怎么判断回文链表，考察的知识点包括链表反转，链表遍历比较
• 题目解答方法的文字分析 ：先使用快慢指针找到链表的中间节点，然后将链表的后半部分反转，最后比较前半部分和后半部分是否相同。
• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

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

        if not head or not head.next:
            return True
        
        slow = fast = head
        #快慢指针找到中间节点
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        if fast:
            slow = slow.next
        #反转后半部分链表
        pre = None
        cur = slow
        while cur:
            next_node = cur.next
            cur.next = pre
            pre = cur
            cur = next_node
        # 比较链表前后两部分,左半部分长度小于等于右边，只要遍历完左边

        left , right = head , pre

        while right:
            if left.val != right.val:
                return False
            left, right = left.next, right.next
        return True