请判断一个链表是否为回文链表。
示例 1:
输入: 1->2 输出: false
示例 2:
输入: 1->2->2->1 输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
**难度**: Easy
**标签**: 链表、 双指针、
# -*- coding: utf-8 -*-
# @Author : LG
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
"""
执行用时：76 ms, 在所有 Python3 提交中击败了90.65% 的用户
内存消耗：23.2 MB, 在所有 Python3 提交中击败了57.77% 的用户
解题思路：
快慢指针，使用慢指针找链表中心，将后半部分翻转
"""
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
fast, slow = head, head
while fast and fast.next: # 快慢指针，快指针是慢指针的2倍速,当快指针到达链表末尾时，慢指针刚好到一半
fast = fast.next.next
slow = slow.next
reverse = None
while slow: # 慢指针翻转链表后半部分
i = slow
slow = slow.next
i.next = reverse
reverse = i
while head and reverse: # 进行比较
if head.val != reverse.val:
return False
head = head.next
reverse = reverse.next
return True