难度: Easy
编写一个函数，检查输入的链表是否是回文的。
示例 1：
输入： 1->2 输出： false
示例 2：
输入： 1->2->2->1 输出： true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
Submission
运行时间: 92 ms
内存: 24.7 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
f = s = head
while f and f.next:
f = f.next.next
s = s.next
if f:
s = s.next
s = self.reverse(s)
while s:
if head.val != s.val:
return False
head = head.next
s = s.next
return True
def reverse(self, head):
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
Explain
此题解采用了快慢指针方法来寻找链表的中点，然后反转链表的后半部分，并与前半部分进行比较以判断是否为回文链表。首先，使用两个指针f（快指针）和s（慢指针），快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末端时，慢指针正好位于链表中间。如果链表长度为奇数，快指针会多出一步，此时需要将慢指针再向前移动一步，以确保后半部分较短。然后，反转从慢指针开始的链表的后半部分。最后，将原链表的头部和反转后的后半部分逐节点比较，若全部节点相等，则链表是回文的。反之，则不是回文链表。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
f = s = head # 初始化快慢指针
while f and f.next:
f = f.next.next # 快指针每次移动两步
s = s.next # 慢指针每次移动一步
if f:
s = s.next # 如果链表长度为奇数，移动慢指针到后半部分的开始
s = self.reverse(s) # 反转后半部分的链表
while s:
if head.val != s.val:
return False # 比较前半部分和反转的后半部分
head = head.next
s = s.next
return True
def reverse(self, head):
pre = None # 反转链表所需的前一个节点初始化为None
cur = head # 当前遍历到的节点
while cur:
tmp = cur.next # 临时保存当前节点的下一个节点
cur.next = pre # 将当前节点的next指向前一个节点
pre = cur # 移动前一个节点到当前节点
cur = tmp # 移动当前节点到下一个节点
return pre # 返回反转后的头结点
Explore
选择快慢指针法来找到链表的中点是为了提高效率和减少空间消耗。使用快慢指针法，我们可以在单次遍历中同时找到中点，这样只需要O(n)的时间和O(1)的额外空间。相比之下，如果先遍历一次链表记录长度，再定位中点，虽然总的时间复杂度仍为O(n)，但需要两次遍历链表，效率较低。此外，记录链表长度还需要额外的空间来存储长度信息。因此，在需要节省空间且提高效率的场景下，快慢指针法是更优的选择。
是的，这种策略适用于所有长度的链表。对于只有一个节点的链表，快指针在第一次移动时就会发现为空，因此循环结束，慢指针仍指向头节点，这时可以正确判断为回文链表。对于两个节点的链表，快指针的第一次移动会指向第二个节点，第二次移动则发现为空，结束循环，此时慢指针指向第二个节点，可以正确进行回文判断。因此，无论链表长度多短，这种快慢指针的移动策略都能正确地处理。
在链表长度为奇数时，额外将慢指针向前移动一步是为了确保比较的是后半部分较短的那一部分与前半部分的对应部分。这是因为，当链表长度为奇数时，中间的元素不需要参与比较（因为回文的中心是一个字符）。如果不将慢指针向前移动，慢指针将从中间元素开始，后半部分将包含中间元素，导致前后比较的长度不一致，无法正确判断回文性。因此，这一步骤对保证算法正确性至关重要。
是的，反转链表的后半部分确实会改变原链表的结构。在这种算法实现中，原本后半部分的链表被反转，使得其节点的顺序和原来完全不同。这种结构的改变是破坏性的，如果在之后的操作中需要使用原始链表的结构，这将是一个问题。因此，在实际应用中，如果需要保持链表原有的结构不变，可能需要在完成回文判断后再次反转后半部分以复原链表，或者采用其他不改变链表结构的方法来判断回文。