LC234 · Palindrome Linked List · 链表

回文链表：慢到中点，反转后半，再比

链表不能从尾巴往回走。先把后半翻过来，比较就变成两条链一起向前。

快指针一次两步、慢指针一次一步，快到尾时慢在中点（偶数个节点时偏右，慢正好是后半起点）。从慢指针起按 LC206 反转后半，prev 成为后半新头。再让原头与 prev 同步前进，值都相等就是回文。奇数多出来的正中节点只跟自己镜像，后半走完即可。时间 O(n)，空间 O(1)。

时间 O(n)空间 O(1)结论先行 · 全文约 6 节

导读

这是 LeetCode 234. Palindrome Linked List。给你一条单链表的头，判断它是不是回文：正着读和倒着读值序列相同。空链、单节点都是回文。

主例 1→2→2→1 是回文；1→2 不是。奇数演示用 1→2→3→2→1，正中的 3 只跟自己镜像。比较场景另走 1→2→1→2→1，两对都相等后判定回文。

数组里左右指针从两头往中间夹就能判。链表只有 Next，没有从尾巴退回来的指针。开数组抄一遍再夹，结果对，但多占 O(n) 空间。缺的是后半段一个可以向前走的头——把后半反转，比较就退化成两条链同步前进。

一

快慢指针找中点

要反转后半，先得知道后半从哪一颗开始。第一直觉是先数长度再走到 n/2，两趟遍历能做对。缺的是一趟就停在中点的办法：让一个指针两倍速，另一个一倍速，快的跑完时慢的正好在一半。

fast、slow 都从头出发。循环条件是 fast 还在且 fast.Next 还在，这样一次跳两步不会空转。每轮 fast 走两步、slow 走一步。fast 撞到尾或尾的 Next 为空时停。

奇数主演示 1→2→3→2→1。第一轮后 slow 在 2、fast 在 3；第二轮后 slow 在 3、fast 在最后的 1。fast.Next 为空，循环停，slow 停在正中的 3，后半从这里开始反转。偶数 1→2→2→1：两轮之后 fast 走出链表，slow 停在第二个 2，正好是后半起点。演示两帧分别钉住这两种停法。

偶数偏右fast 每次跳两步，节点数为偶数时它会走出链表，slow 落在右半的第一颗，而不是两颗中点的左边那颗。后半从这里反转，比较次数正好是 n/2。

fast 两倍速，slow 停在中点

3slow

1fast

slow=3（中点），fast=1（尾）

二

反转后半段

中点有了，后半仍是顺着 Next 往后。要跟前半从头比，必须先把后半的箭头拧过来。用 LC206 的三指针：prev 起手是空，cur 从 slow 出发，每轮暂存 nxt、把 cur.Next 拧向 prev、再滚动 prev 与 cur。cur 走空时，prev 是后半的新头。

奇数 1→2→3→2→1，从正中的 3 反转 3→2→1，得到 1→2→3。演示把比较的两端标成 p1 在原头、p2 在原尾：前半看见 1→2，后半反转后看见 1→2，正中的 3 留在后半新链的尾巴上，比较时会跟自己碰一次，不影响对错。偶数 1→2→2→1 从第二个 2 反转，得到 1→2，两半一样长。

题目不要求还原原链。若面试要求不改输入，比较完再把后半翻回去，步骤对称，不影响判定。

后半段 [3,2,1] 反转为 [1,2,3]

前半段

后半段（已反转）

前半 1→2，后半反转后 1→2

三

双链同步比较

p1 从原头出发，p2 从反转后的 prev 出发。每一步比 Val，不等立刻 false；相等则两指针各走一步。循环看 p2 而不是 p1：后半长度不超过前半，p2 走空就比完了。

比较演示走 1→2→1→2→1。第一帧两端都是 1；第二帧两端都是 2；第三帧全部相等，判定回文。主例 1→2→2→1 同样是两对：1 对 1、2 对 2。1→2 反转后半得到 2，第一对 1 对 2 就失败。

奇数长度后半会多带上正中节点。它只跟自己镜像，最后一次比较一定相等，不必单独跳过。前半多出来的尾巴也不用管——p2 先走完。

p1 与 p2 同步走，逐位相等

1 == 1 ✓

四

Go：找中点 + 反转 + 比较

solution.goGo

func isPalindrome(head *ListNode) bool {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    var prev *ListNode
    for slow != nil {
        nxt := slow.Next
        slow.Next = prev
        prev = slow
        slow = nxt
    }
    l, r := head, prev
    for r != nil {
        if l.Val != r.Val { return false }
        l = l.Next
        r = r.Next
    }
    return true
}

1快慢同起点。必须先看 fast 和 fast.Next 非空，再迈两步，否则偶数长度会解引用空指针。

2从 slow 反转后半。prev 起手 nil，原中点（或右半第一颗）最后变成后半的尾巴。

3反转结束时 prev 是后半新头，l 仍是原头。空链、单节点时 prev 就是原头或 nil，比较循环一次都不进或只比一颗，返回 true。

4只以后半指针 r 为循环条件。第一对不等立刻 false；r 走空则全部配对成功。

总结

慢到中点、反转后半、两链同步比。主例 1→2→2→1 两对都相等。

链表不能后退，缺的是后半一个向前的头，不是「会不会判回文」。
偶数时 slow 停在右半第一颗；奇数时停在正中，多比一次自己不影响对错。
比较看后半指针走空。1→2 第一对 1 对 2 就失败。

同族题目

LC206反转链表LC876链表的中间结点LC9回文数