当前位置：首页 > news >正文

LeetCode-234：回文链表，先做出来，再理解进阶解法

news 2026/3/27 0:45:19

一、题目概述

给定一个单链表的头节点 head，要求判断这条链表是否为回文链表。

所谓回文，就是：

正着读和反着读完全一样。

例如：

示例 1

head = [1, 2, 2, 1]

输出：

True

因为从前往后读是：

1, 2, 2, 1

从后往前读也是：

1, 2, 2, 1

示例 2

head = [1, 2]

输出：

False

因为正着读是：

1, 2

反着读是：

2, 1

二者不同，所以不是回文。

题目还给了一个进阶要求：

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

这意味着，这道题不仅可以“先做出来”，还可以继续优化。

二、最容易想到的思路：先把链表转成列表

这题刚开始最自然的想法其实很直接：

链表不方便从后往前看，那就先把它的值存进列表。

例如链表：

1 -> 2 -> 2 -> 1

转成列表后变成：

[1, 2, 2, 1]

然后只要判断：

原列表
反转后的列表

是否相同即可。

这是最适合初学者理解的做法。

三、列表法代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextdef is_palindrome(head):""":type head: ListNode:rtype: bool"""values = []while head:values.append(head.val)head = head.nextreturn values == values[::-1]

四、列表法逐行拆解

1. 准备一个列表

values = []

这个列表用来存链表中的所有值。

2. 遍历链表，把值加入列表

while head:values.append(head.val)head = head.next

例如链表：

1 -> 2 -> 2 -> 1

遍历结束后：

values = [1, 2, 2, 1]

3. 判断原列表和反转列表是否相同

return values == values[::-1]

这里：

values[::-1]

表示列表倒序。

如果倒序后和原列表一样，就说明这是一个回文序列。

例如：

[1, 2, 2, 1] == [1, 2, 2, 1]

结果为 True。

而：

[1, 2] == [2, 1]

结果为 False。

五、为什么这版代码能做对

因为回文的定义本来就是：

从前往后看，和从后往前看一样。

而列表刚好很容易做“反转后比较”。

所以这版写法虽然不算进阶最优解，但非常适合先建立题感。

六、列表法复杂度分析

设链表长度为 n。

时间复杂度

遍历链表一次：O(n)
列表反转比较一次：O(n)

因此总时间复杂度为：

O(n)

空间复杂度

额外开了一个列表存链表值：

O(n)

所以这版代码不满足题目的进阶要求 O(1) 空间，但完全可以通过题目，并且非常直观。

七、进阶解法的核心思路

如果想做到：

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

那么就不能再额外开一个列表。

这时最经典的做法是：

用快慢指针找到链表中点
反转后半段链表
前半段和后半段逐个比较

这就是这题真正更值得掌握的进阶解法。

八、为什么要这样做

链表之所以难判断回文，是因为它只能从前往后走，不能像数组那样从后往前直接访问。

那怎么办？

可以想办法把“后半段”反过来，这样就变成：

前半段从左往右
后半段反转后也从左往右

然后两个指针一起走，逐个比较即可。

例如：

1 -> 2 -> 2 -> 1

前半段可以看成：

1 -> 2

后半段原本是：

2 -> 1

把后半段反转后变成：

1 -> 2

这样两边就可以直接比较了。

九、进阶解法代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextdef is_palindrome(head):""":type head: ListNode:rtype: bool"""if not head or not head.next:return Trueslow = headfast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextprev = Nonecurr = slowwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodeleft = headright = prevwhile right:if left.val != right.val:return Falseleft = left.nextright = right.nextreturn True

十、进阶解法逐行拆解

1. 特殊情况：空链表或单节点链表

if not head or not head.next:return True

空链表本身就是回文
只有一个节点的链表也是回文

2. 快慢指针找到中点

slow = head
fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.next

这里：

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

当 fast 到达末尾时，slow 就来到链表中间位置。

3. 从中点开始反转后半段链表

prev = None
curr = slow
while curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_node

这段是经典的链表反转操作。

反转完成后：

prev 就是反转后后半段链表的头节点

4. 前后两段开始逐个比较

left = head
right = prevwhile right:if left.val != right.val:return Falseleft = left.nextright = right.next

这里：

left 从链表前半段开始
right 从反转后的后半段开始

只要某一对值不相等，就说明不是回文。

如果全部相同，就说明是回文。

5. 比较完成后返回 `True`

return True

十一、手动模拟一遍进阶解法

以链表：

1 -> 2 -> 2 -> 1

为例。

第一步：找中点

快慢指针最终会让 slow 指向后半部分起点，也就是第二个 2。

第二步：反转后半段

后半段原本是：

2 -> 1

反转后变成：

1 -> 2

第三步：比较前半段和反转后的后半段

前半段从 head 开始：

1 -> 2

后半段从 prev 开始：

1 -> 2

逐个比较：

1 == 1
2 == 2

都相等，因此返回 True。

十二、为什么比较时只写 `while right`

这里很多人会问：为什么不是 while left and right？

因为在这个解法里：

后半段长度一定小于等于前半段长度
回文判断只需要把后半段都比较完就够了

所以只要：

while right:

就可以。

十三、这题的两个层次

这道题非常适合作为“先做出来，再做优化”的练习题。

第一层：列表法

优点：

容易理解
容易实现
很适合初学者建立题感

缺点：

额外用了 O(n) 空间

第二层：快慢指针 + 反转链表

优点：

满足题目进阶要求
时间复杂度 O(n)
空间复杂度 O(1)

缺点：

比列表法更难一些
需要对快慢指针和反转链表都比较熟

所以如果是第一次做这题，先掌握列表法完全没有问题。
在此基础上再理解进阶解法，会更稳。

十四、这题真正训练的是什么

这道题表面上是在判断回文，实际上训练的是三种很重要的链表思维。

1. 链表转列表的直觉

当链表不方便从后往前访问时，先转成数组或列表是一种很自然的思路。

2. 快慢指针找中点

这是链表题里非常经典的技巧。

3. 反转链表

这题的进阶解法其实是在复用链表反转这个基础操作。

也就是说，这道题并不是一个孤立题，而是把几个经典链表技巧串起来了。

十五、小结

“回文链表”这道题可以分成两个层次来掌握。

基础解法：转成列表后判断回文

def is_palindrome(head):values = []while head:values.append(head.val)head = head.nextreturn values == values[::-1]

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

def is_palindrome(head):if not head or not head.next:return Trueslow = headfast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextprev = Nonecurr = slowwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodeleft = headright = prevwhile right:if left.val != right.val:return Falseleft = left.nextright = right.nextreturn True

真正值得记住的，不只是代码，而是这两点：