判断链表回文：从复制到数组到中点逆置

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。判断链表回文是「链表」这一考点里检验双指针和逆置功底的经典组合题，用到的手段和 2019·41 链表重排（找中点 + 逆置）几乎一模一样，只是拼接目标不同——那道题重排，这道题比较。它是经典训练题，不是真题，也不押题。

题目

给定一个单链表的头指针 head，判断该链表是否为回文链表——即链表结点值从前往后读和从后往前读完全一样。例如 1 → 2 → 3 → 2 → 1 是回文，1 → 2 → 3 不是。要求分析时间复杂度和空间复杂度。

链表结点定义如下：

typedef struct node {
    int val;
    struct node *next;
} NODE;

判断回文的期望复杂度是时间 $O(n)$、空间 $O(1)$。先写一个直觉上最容易想到的解法。

第一步：把暴力解写对——复制到数组再双指针比较

判断回文的核心操作是「首尾对应位置的值相等」，这对数组来说是顺手的事——两个下标从两端往中间收拢即可。链表不支持随机访问，最直接的补救是先把所有结点的值顺序复制进一个数组，换来随机访问能力，再在数组上做双指针比较。

#include <stdbool.h>
#include <stdlib.h>

bool isPalindrome(NODE *head) {
    // 数一遍结点个数
    int n = 0;
    for (NODE *p = head; p != NULL; p = p->next) n++;

    // 把结点值顺序复制进数组
    int *vals = (int *)malloc(n * sizeof(int));
    int k = 0;
    for (NODE *p = head; p != NULL; p = p->next) vals[k++] = p->val;

    // 双指针从两端向中间收拢比较
    int i = 0, j = n - 1;
    bool result = true;
    while (i < j) {
        if (vals[i] != vals[j]) { result = false; break; }
        i++;
        j--;
    }

    free(vals);
    return result;
}

拿 1 → 2 → 3 → 2 → 1 走一遍：复制成数组 [1,2,3,2,1]，i=0,j=4 比较 1=1；i=1,j=3 比较 2=2；i=2,j=2 时 i<j 不成立，循环结束，返回 true ✓。拿 1 → 2 → 3 走一遍：数组 [1,2,3]，i=0,j=2 比较 1 与 3，不等，返回 false ✓。

复杂度：数结点、复制数组、双指针比较，三段线性，时间 $O(n)$；额外开了一个长度 n 的数组，空间 $O(n)$。

它值多少分

拓展题按真题同样的两维度看（详见真题专题总纲）：

• 正确性：结点数正确统计、值按序复制、双指针比较逻辑清楚、复杂度分析与实现一致——正确性维度的分拿得到。
• 最优性：判断回文的最优解要求 $O(1)$ 空间。数组复制解的 $O(n)$ 空间达不到，最优性这一档拿不到。

一份写对的数组复制解拿正确性分、丢最优性分。这道题的最优解和 2019·41 用的是同一套「找中点 + 逆置」手法，值得对照着练。

暴力解的浪费在哪

用总纲的「找浪费三问」审这份数组复制解：

有没有放着性质不用？——有。 数组复制解把整条链表的值都搬进了数组，为的是获得「能从后往前读」的能力。但仔细看判断回文这件事，真正需要「反着读」的只有后半段——前半段本来就是顺着读，链表天生支持。为了让后半段也能反着读，暴力解选择把全部结点（包括本来就顺着读没问题的前半段）都搬了一遍。

浪费的本质：为了给后半段配一份「逆序访问」的能力，把整条链表（含不需要这份能力的前半段）都复制进了数组；而让链表后半段支持逆序访问，本身有零额外空间的办法——就地逆置。

智慧化改造：快慢指针找中点 + 后半逆置 + 前后对比

对策是总纲里的第三类手段——利用已知的结构性质。链表逆置本身不需要额外空间，只需要改指针方向；于是最优解浮现为三步：

1. 快慢指针找中点——slow 每步走 1、fast 每步走 2，fast 到尾时把链表切成前后两半；
2. 后半就地逆置——三指针反转（prev/cur/nxt），逆置后从后往前的顺序变成了从前往后；
3. 前后指针同步比较——一个指针从 head 出发，一个指针从逆置后的新头出发，同步前进逐位比较。

#include <stdbool.h>

bool isPalindrome(NODE *head) {
    if (head == NULL || head->next == NULL) return true;

    // ① 快慢指针找中点：slow 停在前半最后一个结点
    NODE *slow = head, *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // ② 截下后半并就地逆置
    NODE *second = slow->next;
    slow->next = NULL;                        // 先切断，再逆置
    NODE *prev = NULL, *cur = second, *nxt;
    while (cur != NULL) {
        nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }

    // ③ 前半指针 p1、逆置后的后半指针 p2 同步比较
    NODE *p1 = head, *p2 = prev;
    bool result = true;
    while (p2 != NULL) {
        if (p1->val != p2->val) { result = false; break; }
        p1 = p1->next;
        p2 = p2->next;
    }

    return result;
}

从数组复制解升级过来，几处最容易翻车：

• 快慢指针的循环条件必须是 fast->next != NULL && fast->next->next != NULL，这决定了中点切分是否精确——和 2019·41 里的坑完全一样，写错会让奇数长度链表的切分点偏移。
• 先切断再逆置：slow->next = NULL 必须在反转开始之前执行，否则前后两半在逆置过程中会纠缠。
• 比较循环以 p2 != NULL 为准，而不是 p1 != NULL——后半段逆置后长度小于等于前半段，用较短的一侧控制循环边界，天然避免越界。
• 偶数长度和奇数长度都不需要跳过中间结点：奇数长度时中间结点只属于前半（slow 停在它上面），后半逆置和比较都不会碰到它，无需特殊处理。

复杂度：找中点、逆置、比较各扫半条链，时间 $O(n)$；全程只有固定几个指针变量，空间 $O(1)$。这就是把数组复制解的 $O(n)$ 空间彻底消除后的结果。

两版对照跑一遍

同一条链表 1 → 2 → 3 → 2 → 1（回文）。先看数组复制版：

加载可视化中...

再看快慢指针 + 逆置版——注意后半段被就地反转,全程没有出现任何数组：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

• 压栈法：把前半段值依次入栈，后半段边遍历边出栈比较，效果等价于数组复制解，同样是 $O(n)$ 空间，只是容器从数组换成栈，判分定位不变。
• 和 2019·41 的关系：这道题与链表重排共享同一套「快慢指针找中点 + 就地逆置」的手段，但目标不同——重排是把两段交叉拼接回一条链，回文判断是把两段拿来比较后即可结束，不需要把链表复原。若题目要求判断后保持链表结构不变，可以在比较完成后再把后半段逆置回去，多付出一次 $O(n)$ 时间，空间仍是 $O(1)$。
• 为什么不用递归：用递归配合一个全局/引用传递的前指针也能做到判断回文，但递归栈本身占用 $O(n)$ 空间，并不比数组复制解更优，408 语境下不作为首选最优解。

下一步

• 看单链表基础操作的交互演示：单链表可视化
• 回到方法论源头：「暴力解到最优解」真题专题总纲
• 找中点 + 逆置的手段同样出现在：2019·41 链表重排、单链表判环

相关真题（1题）

2017Q11选择题2分

去刷题

链式存储排序：链式存储对各排序算法效率的影响

单链表