题解 | #判断一个链表是否为回文结构#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head: ListNode) -> bool:
        if not head:
            return False
        if not head.next:
            return True
        
        left = head
        right = head
        a = []
        while right and right.next:
            # 通过双指针找到中间位置
            a.append(left.val)
            left = left.next
            right = right.next.next
        
        if not right:
            # ABBA 型
            while left:
                if left.val != a.pop():
                    return False
                left = left.next
            return True
        elif not right.next:
            # ABA 型
            # 此时的left指向了中间的位置，所以需要下移一位
            left = left.next
            while left:
                if left.val != a.pop():
                    return False
                left = left.next
            return True