算法

回文链表

loser

20 Aug 2026 • 8 min read

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true
示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法一（数组 + 双指针）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> values;

        ListNode* cur = head;
        while (cur != nullptr)
        {
            values.push_back(cur->val);
            cur = cur->next;
        }

        int left = 0;
        int right = values.size() - 1;

        while (left < right)
        {
            if (values[left] != values[right])
            {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
};

解法二（快慢指针 + 反转后半段）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
        {
            return true;
        }

        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool ans = true;

        while (p2 != nullptr)
        {
            if (p1->val != p2->val)
            {
                ans = false;
                break;
            }

            p1 = p1->next;
            p2 = p2->next;
        }

        firstHalfEnd->next = reverseList(secondHalfStart);

        return ans;
    }

private:
    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast->next != nullptr && fast->next->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;

        while (cur != nullptr)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
};

核心思想

这题要判断链表中的值序列是否回文。

如果是数组，直接用两个指针从两端往中间比较即可。

但链表的问题是：

只能从前往后走
不能直接访问最后一个节点
也不能像数组一样用下标随机访问

所以最直观的做法是先把链表值存进数组，再用双指针判断。

这个方法简单，但需要 O(n) 额外空间。

进阶要求 O(1) 空间，所以需要直接在链表上处理。

这题最关键的观察是：

判断回文只需要比较前半段和反转后的后半段。

也就是说，我们可以先找到链表的中点，把后半段反转，然后让前半段和反转后的后半段逐个比较。

解法一：数组 + 双指针

先遍历链表，把所有节点值存入数组：

values.push_back(cur->val);

这样链表问题就变成了数组回文判断问题。

然后使用两个指针：

left 指向数组开头
right 指向数组末尾

每次比较：

values[left] == values[right]

如果发现不相等，直接返回 false。

如果所有对称位置都相等，返回 true。

这个方法不会修改链表结构，但需要额外数组保存所有值。

解法二：快慢指针 + 反转后半段

为了做到 O(1) 空间，我们不能把所有节点值复制到数组中。

可以分三步完成。

1. 找到前半段的尾节点

使用快慢指针：

slow 每次走一步
fast 每次走两步

当 fast 走到链表末尾时，slow 就在链表中间附近。

代码中使用：

while (fast->next != nullptr && fast->next->next != nullptr)

循环结束后，slow 就是前半段的最后一个节点。

例如：

[1,2,2,1]

前半段尾节点是第一个 2。

对于奇数长度：

[1,2,3,2,1]

前半段尾节点是中间节点 3。

中间节点不影响回文判断，后续只比较后半段长度即可。

2. 反转后半段链表

从：

firstHalfEnd->next

开始反转后半段。

例如：

1 -> 2 -> 2 -> 1

后半段是：

2 -> 1

反转后变成：

1 -> 2

这样就可以和前半段从头开始逐个比较。

3. 比较前半段和后半段

使用两个指针：

p1 从 head 出发
p2 从反转后的后半段头节点出发

只要 p2 还没有走完，就比较：

p1->val == p2->val

如果某一对值不同，说明不是回文链表。

如果后半段全部比较完都相同，说明链表是回文链表。

最后把后半段再反转一次接回去：

firstHalfEnd->next = reverseList(secondHalfStart);

这样函数返回后，链表结构仍然和原来一致。

为什么只比较后半段长度

对于偶数长度链表，例如：

[1,2,2,1]

前半段和后半段长度相同。

反转后半段后，两边逐个比较即可。

对于奇数长度链表，例如：

[1,2,3,2,1]

中间节点 3 不需要参与比较。

回文只要求它左边和右边对称相等。

代码中的 endOfFirstHalf 会让 firstHalfEnd 停在中间节点。

所以后半段从中间节点之后开始：

firstHalfEnd->next

比较时只让 p2 控制循环：

while (p2 != nullptr)

就可以自然跳过中间节点。

边界情况

链表至少有一个节点。

如果链表只有一个节点，它一定是回文链表。

代码中直接处理：

if (head == nullptr || head->next == nullptr)
{
    return true;
}

虽然题目保证节点数至少为 1，保留 head == nullptr 判断也没有问题。

如果链表长度为 2，例如：

[1,2]

前半段尾节点是第一个节点，后半段是第二个节点。

比较两个值不同，返回 false。

正确性证明

我们证明：解法二返回的结果满足题意。

结论 1：`endOfFirstHalf` 能正确找到前半段尾节点

快指针 fast 每次走两步，慢指针 slow 每次走一步。

当 fast 不能继续走两步时，说明慢指针已经走到前半段末尾。

对于偶数长度链表，slow 停在前半段最后一个节点。

对于奇数长度链表，slow 停在中间节点。

这正好满足后续从 slow->next 开始处理后半段的需要。

结论 2：反转后半段后，可以按同一方向比较两侧节点

原链表如果是回文，那么后半段从左到右的顺序，应该等于前半段从右到左的顺序。

把后半段反转以后，它的顺序就变成了原链表从右往左的顺序。

因此，前半段从头开始，反转后的后半段也从头开始，两个指针逐个比较，就等价于比较原链表的对称位置。

结论 3：如果比较过程中出现不同值，链表一定不是回文

比较过程中，p1 和 p2 指向的是一组对称位置。

如果：

p1->val != p2->val

说明至少有一组对称位置的节点值不同。

根据回文定义，链表不可能是回文链表。

所以返回 false 正确。

结论 4：如果后半段全部比较通过，链表一定是回文

比较循环由 p2 控制。

p2 会遍历反转后的整个后半段。

如果所有比较都相等，说明链表右半部分的每个节点，都和左半部分对应位置相等。

对于奇数长度链表，中间节点不影响回文判断。

因此链表满足回文定义。

得出结论

由结论 1 可知，算法正确划分前半段和后半段。

由结论 2 可知，反转后半段后可以逐个比较对称节点。

由结论 3 和结论 4 可知，比较结果与回文定义完全一致。

因此算法正确。

举例理解

以：

head = [1,2,2,1]

为例。

先用快慢指针找到前半段尾节点：

前半段：1 -> 2
后半段：2 -> 1

反转后半段：

1 -> 2

然后比较：

前半段第一个节点 1，后半段第一个节点 1，相等
前半段第二个节点 2，后半段第二个节点 2，相等

所以返回 true。

再看：

head = [1,2]

前半段是：

后半段反转后仍然是：

比较发现 1 != 2，所以返回 false。

复杂度分析

解法一

需要遍历链表一次把值存入数组，再用双指针比较数组。

时间复杂度：O(n)
空间复杂度：O(n)

解法二

快慢指针找中点、反转后半段、比较、恢复链表，每一步都是线性时间。

整体仍然是：

时间复杂度：O(n)
空间复杂度：O(1)

解法二满足进阶要求，是更推荐的做法。