234 回文链表（翻转链表）

1. 问题描述：

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

2. 思路分析：

判断一个回文数字我们可以使用两个指针分别从前往后与从后往前的依次判断元素值是否相等，对于链表的操作也是类似的，只是我们需要找到链表的中间位置，所以一开始的时候需要遍历一遍链表元素，计算链表的总长度，然后从前往后找到链表的中间位置，使得一个指针指向链表的中间位置然后就可以对链表的后半部分进行翻转，通过一个指针指向链表的尾节点这样就可以通过两个指针从前往后与从后往前判断元素值是否相等来判断是否是回文链表，最后需要将后半部分翻转之后的链表恢复为之前的状态即可。

3. 代码如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        n = 0
        a = head
        while a:
            n += 1
            a = a.next
        if n <= 1: return True
        half = n // 2
        a = head
        # a经过循环之后指向的是链表的中间位置
        for i in range(n - half):
            a = a.next
        b = a.next
        # 翻转后半部分列表
        for i in range(half - 1):
            c = b.next
            b.next = a
            a = b
            b = c
        p = head
        q = a
        f = 1
        # 判断是否是回文链表
        for i in range(half):
            if p.val != q.val:
                f = 0
                break
            p = p.next
            q = q.next
        b = a.next
        # 将之前翻转的列表恢复为之前的状态
        for i in range(half - 1):
            c = b.next
            b.next = a
            a = b
            b = c
        a.next = None
        return f == 1