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

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

描述 给定一个链表，请判断该链表是否为回文结构。 回文是指该字符串正序逆序完全一致。

数据范围： 链表节点数 0≤n≤10^7，链表中每个节点的值满足 ∣val∣≤^7

解法：快慢指针，将链表分成两部分，前半部分的长度=后半部分的长度（+1），然后后半部分逆序（之前的有做过逆序的题目，这里直接拿来用了），之后比较两部分的值是否相等。

```# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    @staticmethod
    def ReverseList(pHead):
        if pHead == None:
            return None
        cur_pointer = pHead
        pre_pointer = None
        next_pointer = None
        while (cur_pointer != None):
            next_pointer = cur_pointer.next
            cur_pointer.next = pre_pointer
            pre_pointer = cur_pointer
            cur_pointer = next_pointer
        return pre_pointer
    def isPail(self , head: ListNode) -> bool:
        # write code here
        if head == None:
            return True
        if head.next == None:
            return True
        slow = head
        fast = head.next
        while fast != None:
            if fast.next == None:
                break
            slow = slow.next
            fast = fast.next.next
        head1 = slow.next
        slow.next = None
        head1 = self.ReverseList(head1)
        node = head
        node1 = head1
        while node1 != None:
            if node1.val != node.val:
                return False
            node = node.next
            node1 = node1.next
        return True