难度: Easy
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true
示例 2：
输入：head = [1,2] 输出：false
提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
Submission
运行时间: 76 ms
内存: 24.8 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 head is None or head.next is None:
return True
s = f = head
while f and f.next:
f = f.next.next
s = s.next
if f is not None:
s = s.next
def reverse(head):
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
right = reverse(s)
left = head
while right:
if right.val != left.val:
return False
right = right.next
left = left.next
return True
Explain
该题解的思路是将链表分为两半，反转后半部分链表，然后同时遍历前半部分和反转后的后半部分，依次比较对应节点的值是否相等。首先通过快慢指针找到链表的中点，慢指针每次走一步，快指针每次走两步，当快指针到达链表尾部时，慢指针刚好到达中点。如果链表节点数为奇数，则中点后一个节点才是后半部分的起点。然后反转后半部分链表，再同时遍历比较两个链表的节点值是否相等，如果都相等则说明是回文链表，否则不是回文链表。
时间复杂度: 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:
# 如果链表为空或者只有一个节点，直接返回 True
if head is None or head.next is None:
return True
# 初始化快慢指针
s = f = head
# 找到链表的中点
while f and f.next:
f = f.next.next
s = s.next
# 如果链表节点数为奇数，则中点后一个节点才是后半部分的起点
if f is not None:
s = s.next
# 反转链表的函数
def reverse(head):
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
# 反转后半部分链表
right = reverse(s)
left = head
# 同时遍历前半部分和反转后的后半部分，比较对应节点的值是否相等
while right:
if right.val != left.val:
return False
right = right.next
left = left.next
return True
Explore
快慢指针策略中，快指针每次移动两步，慢指针每次移动一步。当快指针无法继续移动（即到达链表尾部）时，慢指针则正好位于中点。对于偶数节点的链表，当快指针的下一个节点为null时，慢指针位于中间两个节点的第一个；对于奇数节点的链表，当快指针自身为null时，慢指针位于中间节点。因此，在奇数长度的链表中，为了使后半部分与前半部分长度相同，需要将慢指针向前移动一位，从而跳过正中间的节点。
当链表只有一个节点时，反转操作非常简单。在反转函数中，该节点会被设置为当前节点（cur），而前一个节点（pre）被设置为null。遍历开始时，将当前节点的next指针指向前一个节点，即null，然后更新前节点为当前节点，当前节点移动到下一个节点，即null。因此，反转后的链表头仍然是原链表的唯一节点，其next指针指向null，表示链表结束。
在判断回文链表时，如果链表的节点数为奇数，中间的节点不需要与任何节点比较，因为它自身就是对称的中心。因此，为了简化比较过程，我们可以跳过这个中间节点，直接从它的下一个节点开始反转后半部分链表。这样做可以确保前后两部分长度相等，便于直接比较。如果包括中间节点在内，前后两部分的长度将不一致，无法进行有效的一对一比较。
比较两个链表的节点值时，结束条件是右半部分（已被反转的后半部分）的链表节点被完全遍历完毕。由于反转后的右半部分链表长度与左半部分链表长度相同（或在奇数节点链表中略短一节点），因此，当右半部分遍历完毕时，左半部分链表对应的部分也刚好遍历完毕。这确保了每个节点都被比较过，无需单独检查左半部分是否遍历完毕。