题目
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。
示例 1：
输入：head = [1,2,2,1]
输出：true
提示
一句话思路：先找链表中间节点，反转后半段，再逐个比较前后两半是否相同。
- 找中间节点用快慢指针：
slow每次走一步，fast每次走两步，fast到末尾时slow正好在中点。 - 反转从
mid开始的后半段，得到head2，然后让head（前半段）和head2（反转后的后半段）从头同步比较。 - 前半段和后半段长度相等（奇数个节点时中间节点被归入后半段，不影响比较结果），有任一节点不同就不是回文。
- 时间 O(n)、空间 O(1)（不额外开辟链表，反转是原地操作）。
答案
python
class Solution:
# 876. 链表的中间结点
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head # 快慢指针都从头节点出发
while fast and fast.next: # fast 每次能走两步才继续
slow = slow.next # slow 每次走一步
fast = fast.next.next # fast 每次走两步
return slow # fast 到末尾时，slow 正好在中间节点
# 206. 反转链表
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, cur = None, head # pre 已反转头，cur 当前节点
while cur: # 遍历到链表末尾
nxt = cur.next # 暂存后继节点
cur.next = pre # 当前节点指向前一个节点（反转）
pre = cur # pre 前进
cur = nxt # cur 前进到原后继节点
return pre # 反转后的链表头
def isPalindrome(self, head: Optional[ListNode]) -> bool:
mid = self.middleNode(head) # 找中间节点
head2 = self.reverseList(mid) # 反转后半段
while head2: # 逐对比较前后两半
if head.val != head2.val: # 对应节点值不同
return False # 不是回文链表
head = head.next # 前半段指针后移
head2 = head2.next # 后半段指针后移
return True # 全部相同，是回文链表
留言板