题目：回文链表

分析

这道题目标签为简单题，但是如果要实现下面的进阶过程不是很简单。

拿到题目一般来说就是赶时间，没有要求的情况下直接使用一个列表存储所有的数值，然后判断这个列表是否满足回文，这个思路是比较简单的，代码如下：

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head: return False
        cur = head
        nums = []
        while cur:
            nums.append(cur.val)
            cur = cur.next
        n = len(nums)
        for i in range(n // 2):
            if nums[i] != nums[n - 1 - i]:
                return False
        return True

但是，如果要完成下面的进阶部分，也即在$\mathcal{O}(1)$的空间复杂度实现，需要综合运用如下知识：

• 双指针求链表中位数
• 链表翻转

下面将一步一步实现这个过程

# 特殊情况考虑直接返回
# 1. None或者只有1个节点
if not head:
    return False

if not head.next:
    return True

查找链表的中间节点，为了前半部分能够正常闭合，所以需要当链表长度为偶数的时候，指针指向前一个值。

# 停止时slow指向中间位置的前一个，此时的fast和slow起始位置不同步
slow, fast = head, head.next

# 因为fast每次移动两个单位，所以需要保证fast和fast.next同时存在
# 否则会报错
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# 此时slow指向中间位置的靠前一个
# 先保存slow.next作为后半部分的起始值
cur = slow.next
# 将前半部分进行闭合
slow.next = None

将后半部分翻转

# 根据前面保存的cur，从cur开始将链表翻转
pre = None
while cur:
    tmp = cur.next
    cur.next = pre
    pre = cur
    cur = tmp
# 翻转结束时pre指向最后一个节点

比较是否满足回文

# 前半部分链表的起始值为head
# 后半部分的起始值为pre
cura = head # 避免头结点找不到
curb = pre
while cura and curb:
    if curb.val != cura.val:
        break
    cura = cura.next
    curb = curb.next
# 不能直接返回，而是跳出循环，因为还要进行链表还原

# 还原过程
# 前一个链表的起点是head
# 后一个链表的起点是pre
cur = pre
pre = None
while cur:
    tmp = cur.next
    cur.next = pre
    pre = cur
    cur = tmp
    
# 此时pre指向后半部分的开始值
# 将前半部分和后半部分连接起来
cur = head
while head.next:
    head = head.next
    
head.next = pre

if cura and curb:
    return False
return True

综上，总体代码为：

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 特殊情况
        if not head:
            return False
        if not head.next:
            return True
        
        # 找到中点，翻转后半部分
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # slow 指向中间位置或者中间靠后一个位置
        
        # 翻转后半段链表
        cur = slow.next
        # 将前半段与后半段分割
        slow.next = None
        pre = None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        
        cura, curb = head, pre
        while cura and curb:
            if cura.val != curb.val:
                break
            cura = cura.next
            curb = curb.next
        
        print(pre.val)
        print(head.val)
        
        # 链表还原
        cur = pre
        pre = None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        # last point
        # pre
        
        cur = head
        while cur.next:
            cur = cur.next
        cur.next = pre
        
        if cura and curb:
            return False
        return True