难度: Easy
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例 1：
输入: head = [1,2,3,3,2,1] 输出: true
示例 2：
输入: head = [1,2] 输出: false
提示：
[1, 105]0 <= node.val <= 9进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
注意：本题与主站 234 题相同：https://leetcode-cn.com/problems/palindrome-linked-list/
运行时间: 239 ms
内存: 28.1 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head: return True
# 找中点
fast, slow, prev = head, head, None
while fast.next and fast.next.next:
fast = fast.next.next
temp = slow.next
slow.next, prev, slow = prev, slow, temp
# 比较回文
if fast.next:
fast = slow.next
slow.next = prev
else:
fast = slow.next
slow = prev
while slow:
if fast.val != slow.val:
return False
fast, slow = fast.next, slow.next
return True
此题解采用了快慢指针法来找到链表的中点，并在此过程中反转链表的前半部分。快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针则位于中点。若链表长度为奇数，慢指针还需前进一步。之后，从中点将链表分为前后两部分，前半部分已在移动时被反转。然后分别从前半部分和后半部分的头部开始比较，若所有对应节点值相等，则链表为回文链表。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head: return True # 如果链表为空，直接返回True
# 初始化快慢指针和前序节点
fast, slow, prev = head, head, None
# 使用快慢指针找到中点，同时反转前半部分链表
while fast.next and fast.next.next:
fast = fast.next.next
temp = slow.next
slow.next, prev, slow = prev, slow, temp
# 调整指针，准备比较回文
if fast.next:
fast = slow.next
slow.next = prev
else:
fast = slow.next
slow = prev
# 比较前半部分和后半部分是否相等
while slow:
if fast.val != slow.val:
return False
fast, slow = fast.next, slow.next
return True
在反转链表的同时使用快慢指针可以有效地减少算法的时间复杂度和空间复杂度。如果先使用快慢指针定位到中点，然后再对前半部分进行反转，这样做虽然可行，但会导致需要两次遍历链表：一次是找中点，一次是反转前半部分。而同时操作可以仅通过一次遍历完成中点查找和前半部分的反转，从而使得整体效率更高。
条件`fast.next and fast.next.next`是为了确保快指针在移动时不会越界，同时可以确保快指针总是走两步，慢指针走一步。当链表长度为偶数时，快指针会停在链表的最后一个节点上，这时慢指针正好在中间位置的第一个节点上。而当链表长度为奇数时，快指针会停在倒数第二个节点上，这时慢指针位于中间位置的节点上。因此，在偶数长度的情况下，需要额外处理使慢指针前进一步至确切的中点位置。
在代码中，根据快指针的位置（是否有next节点）来调整慢指针的位置，以适应奇偶长度的链表。如果快指针有next节点（即长度为偶数），慢指针会前进到偶数链表的中间位置开始比较。如果快指针没有next节点（即长度为奇数），慢指针则不需要前进，因为它已经位于中间。然后通过调整指针，将慢指针的前半部分链表与后半部分进行比较，通过节点值比较来判断是否为回文链表。