回文链表

问题拆解

判断单链表是不是回文。数组做法很简单：把值复制到列表里，用双指针从两端向中间比。但那是 O(n) 空间。

进阶要求 O(1) 空间。链表没法从尾往前走，所以关键是想办法让“后半段”能被正向遍历——把后半段原地反转，再和前半段逐一对照即可。

三步走：快慢指针找到中点，反转后半段，然后从两头同时向中间比较。整个过程只借用几个指针。

找中点 + 反转后半

def isPalindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt

    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

快指针一次两步、慢指针一次一步，快指针到头时慢指针正好落在后半段的起点（长度为奇数时落在正中，中间那个节点不影响比较）。接着用三指针把从 slow 开始的后半段反转，prev 成为反转后的新头，也就是原链表的尾节点。

比较时让 left 从头、right 从尾（反转后的头）同时往中间走。因为后半段更短或等长，以 right 走空作为结束条件即可，前半段多出来的中间节点不必比。

复杂度

指标	复杂度	原因
时间	O(n)	找中点、反转、比较各扫描一部分，合计线性
空间	O(1)	只用若干指针，原地反转后半段

可以迁移的模式

• “从两端向中间比”在链表里做不到，就把后半段反转成可正向遍历；
• 快慢指针找中点是拆分链表的通用前置步骤；
• 需要 O(1) 空间时，优先考虑原地改指针，而不是复制数据。

这道题是链表基本操作的组合练习：中点、反转、比较三个小技能各来一次。