16、链表的回文判断：快慢指针+反转法、数组辅助法

回文判断，说白了就是检查一个链表正着读和反着读是不是一样。比如 1→2→3→2→1 就是回文，1→2→3→4 就不是。

这个问题我在实际项目中遇到过几次。有一次是做数据校验模块，需要判断历史操作序列是否对称。当时数据量很大，用数组辅助法内存吃不消，最后选了快慢指针+反转法。嗯，这里面的坑还真不少，咱们一个一个说。

什么是回文链表？

回文链表有两个特点：

• 正向遍历和反向遍历的结果相同
• 链表结构对称，中间节点（或中间两个节点）是分界点

举个例子：

回文：1 → 2 → 3 → 2 → 1
回文：1 → 2 → 2 → 1
非回文：1 → 2 → 3 → 4

你想想看，判断回文最直接的办法是什么？把链表反转，然后比较原链表和反转后的链表。但这样做需要额外复制一份链表，空间复杂度 O(n)。

有没有更好的办法？当然有。我习惯用快慢指针定位中点，然后反转后半段，再比较前后两段。这样空间复杂度能降到 O(1)。

方法一：快慢指针 + 反转法

这个方法的核心思路分三步：

1. 找中点：快指针每次走两步，慢指针每次走一步。快指针到末尾时，慢指针正好在中点。
2. 反转后半段：从中点开始，反转后半部分链表。
3. 比较前后段：同时遍历前半段和反转后的后半段，逐个比较节点值。

来看代码实现：

#include <stdio.h>
#include <stdbool.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode *prev = NULL, *curr = head, *next = NULL;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 判断回文
bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;

    // 1. 快慢指针找中点
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 2. 反转后半段
    ListNode *secondHalf = reverseList(slow);
    ListNode *firstHalf = head;
    ListNode *temp = secondHalf;  // 保存用于恢复

    // 3. 比较前后段
    while (secondHalf) {
        if (firstHalf->val != secondHalf->val) {
            // 恢复链表（可选）
            reverseList(temp);
            return false;
        }
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }

    // 恢复链表（可选）
    reverseList(temp);
    return true;
}

方法二：数组辅助法

这个方法更直观：遍历链表，把所有节点值存到数组里，然后用双指针从数组两端向中间比较。

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

bool isPalindromeArray(ListNode* head) {
    if (!head || !head->next) return true;

    // 1. 计算链表长度
    int len = 0;
    ListNode *curr = head;
    while (curr) {
        len++;
        curr = curr->next;
    }

    // 2. 申请数组
    int *arr = (int*)malloc(len * sizeof(int));
    if (!arr) return false;

    // 3. 复制到数组
    curr = head;
    for (int i = 0; i < len; i++) {
        arr[i] = curr->val;
        curr = curr->next;
    }

    // 4. 双指针比较
    int left = 0, right = len - 1;
    while (left < right) {
        if (arr[left] != arr[right]) {
            free(arr);
            return false;
        }
        left++;
        right--;
    }

    free(arr);
    return true;
}

两种方法对比

对比项	快慢指针+反转法	数组辅助法
时间复杂度	O(n)	O(n)
空间复杂度	O(1)	O(n)
代码复杂度	中等	简单
是否修改链表	会（需恢复）	不会
适用场景	内存受限、大数据量	小数据量、快速实现

说白了，选哪种方法取决于你的场景。如果内存够用、数据量不大，数组辅助法写起来快、不容易出错。如果内存紧张或者链表很长，快慢指针法更合适。

核心逻辑流程图

下面这张图展示了快慢指针+反转法的完整流程：

边界情况处理

写代码时，边界情况最容易出问题。我总结了几点：

• 空链表或只有一个节点：直接返回 true，这是回文。
• 链表节点数为奇数：比如 1→2→3→2→1，快慢指针找中点时，slow 停在 3。反转后半段后，前半段是 1→2→3，后半段是 1→2。比较时前半段多了一个中间节点 3，但不需要比较它。
• 链表节点数为偶数：比如 1→2→2→1，slow 停在第二个 2。反转后半段后，前半段是 1→2，后半段是 1→2，正好一一对应。
• 恢复链表：如果后续还要用原链表，记得把反转的后半段再反转回来。

实际项目中的选择

我在嵌入式项目里用过这两种方法。有一次做数据采集系统，链表里存了上万个采样点，需要判断数据是否对称。当时内存只有 64KB，数组辅助法根本不敢用——万一 malloc 失败，系统就崩了。

最后我选了快慢指针法，空间复杂度 O(1)，稳稳的。不过要注意，反转链表会修改原始数据，所以我比较完之后立刻恢复了链表结构。

如果你是在 PC 上写算法题，数组辅助法更省事。但如果你做嵌入式开发，我建议你养成用快慢指针法的习惯——内存紧张时，这个技能能救命。

---

好了，回文判断就讲到这里。两种方法各有优劣，关键是根据场景选对工具。代码写完了，记得多测几个边界情况，尤其是奇数和偶数长度的链表。