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

# 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:
        # write code here
        # 知识点头插法和尾插法的顺序是天然相反的，但是需要知道列表的数量
        ret = True
        # 至少有两个节点的时候，进一步处理
        if head and head.next:
            # 假的头节点用于头插法
            p1 = head
            p2 = head
            # 计算节点数量
            count = 0
            while p1:
                count += 1
                p1 = p1.next
            # print(f"list length is {count}")
            p1 = ListNode(0)

            move_count = int(count/2)
            # 移动到中心点附近
            # 3/2 = 1
            # 2/2 = 1
            for i in range(move_count):
                # p2的新位置
                p3 = p2.next
                # 头插法
                p2.next = p1.next
                p1.next = p2
                p2 = p3
            if 0 == count%2:
                # 如果数量是偶数
                pass
            else:
                # 如果数量是奇数
                # 直接跳过中心点
                p2 = p2.next
            # 链表对半分
            p1 = p1.next
            while p1:
                if p1.val != p2.val:
                    ret = False
                    break
                else:
                    p1 = p1.next
                    p2 = p2.next
        # 无节点或单一节点直接返回
        return ret