466 lines
15 KiB
Markdown
466 lines
15 KiB
Markdown
---
|
||
tags: ["LeetCode", "链表", "双指针", "反转链表", "递归", "简单"]
|
||
create time: 2026-05-16 14:40
|
||
---
|
||
|
||
# 24-回文链表
|
||
|
||
## 题面
|
||
|
||
给你一个单链表的头节点 `head`，请你判断该链表是否为回文链表。如果是，返回 `true`；否则，返回 `false`。
|
||
|
||
**示例 1：**
|
||
|
||
```
|
||
输入：head = [1,2,2,1]
|
||
输出：true
|
||
```
|
||
|
||
**示例 2：**
|
||
|
||
```
|
||
输入：head = [1,2]
|
||
输出：false
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- 链表中节点数目在范围 `[1, 10^5]` 内
|
||
- `0 <= Node.val <= 9`
|
||
- **进阶：** 你能否用 `O(n)` 时间复杂度和 `O(1)` 空间复杂度解决此题？
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 核心洞察
|
||
> 回文的本质是"前后对称"——前半段和后半段镜像相同。对数组来说我们天然可以随机访问，可以直接对比 `arr[i] == arr[n-1-i]`。但**链表只能顺序遍历，无法从后往前看**，这是解题的最大障碍。
|
||
|
||
> [!warning] ⚠️ 关键差异：数组 vs 链表
|
||
> | 特性 | 数组 | 链表 |
|
||
> |------|------|------|
|
||
> | 正序遍历 | O(1)（直接索引） | O(1)（next 指针） |
|
||
> | 逆序遍历 | O(1)（反向索引） | ❌ 不支持，必须走一遍 |
|
||
> | 中间点定位 | O(1)（`(n-1)/2`） | 需要遍历 |
|
||
>
|
||
> 所以挑战在于：**如何在只走一遍或常数次遍历时拿到"后半段的逆序"？**
|
||
|
||
### 方法一：栈 / 切片法（直觉方案）
|
||
|
||
把每个节点的值依次压入栈（或存进切片），然后再次从头遍历链表，将节点值与栈顶（或切片末尾）逐个比较。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph "第一轮：收集数据"
|
||
H["head → 1→2→2→1"] --> S["stack: [1,2,2,1]"]
|
||
end
|
||
|
||
subgraph "第二轮：对比"
|
||
H2["head → 1→2→2→1"] --> C["对比：top==val? yes → yes → yes → yes"]
|
||
end
|
||
|
||
C --> RESULT["✅ true"]
|
||
style RESULT fill:#4c4,stroke:#333
|
||
```
|
||
|
||
**步骤拆解：**
|
||
|
||
| 轮次 | 动作 | 代价 |
|
||
|------|------|------|
|
||
| 第 1 轮 | 遍历全链表，将所有 val 存入栈/切片 | O(n) |
|
||
| 第 2 轮 | 重新遍历链表，每次取栈顶对比当前 val | O(n) |
|
||
|
||
**时间复杂度：O(n)** — 两次线性遍历。
|
||
**空间复杂度：O(n)** — 需要额外的栈存储所有元素。
|
||
|
||
> [!note] 🤔 这个方法的问题是什么？
|
||
> 完全满足时间要求，但不满足进阶的 O(1) 空间。而且它做了**两次完整遍历**——如果能把后半段原地翻转，就能避免额外空间和重复遍历。
|
||
|
||
---
|
||
|
||
### 方法二：快慢指针 + 反转后半段 ⭐（最优，O(1) 空间）⭐
|
||
|
||
这是进阶问题的标准解法，核心思路分三步：**找到中点 → 反转后半段 → 逐一对比**。
|
||
|
||
#### 第一步：用快慢指针找中点
|
||
|
||
> [!question] 💡 为什么快慢指针能找中点？
|
||
> 让快指针每次走两步、慢指针每次走一步。当快指针到达终点时，慢指针恰好走到中间——因为快指针的速度是慢指针的两倍，路程也是两倍。
|
||
|
||
> [!tip] 🔑 关键细节：初始化 fast 为 `head.Next`
|
||
> 如果两个指针都从 `head` 开始，偶数长度链表的比较会出现问题（见下方分析）。标准写法是将 fast 初始化在第二个节点上：
|
||
|
||
```go
|
||
slow, fast := head, head.Next
|
||
```
|
||
|
||
以 `1→2→2→1`（偶数长度）为例：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph "初始"
|
||
A["快=2, 慢=1"]
|
||
end
|
||
|
||
subgraph "第1步"
|
||
B["快=1, 慢=2"]
|
||
end
|
||
|
||
subgraph "退出"
|
||
C["快=nil, 慢=2 ★中点"]
|
||
end
|
||
|
||
A -.两步.-> B -.两步.-> C
|
||
style C fill:#f9d,stroke:#333
|
||
```
|
||
|
||
详细过程：
|
||
|
||
| 步数 | fast 位置 | slow 位置 | fast!=nil && fast.Next!=nil |
|
||
|------|----------|----------|-----------------------------|
|
||
| 开始前 | 2 | 1 | ✅ 继续 |
|
||
| 第 1 轮后 | 1 | 2 | ✅ 继续 |
|
||
| 第 2 轮后 | nil | 2 | ❌ fast == nil，退出 |
|
||
|
||
对于奇数长度的链表 `1→2→3→2→1`：
|
||
|
||
| 步数 | fast 位置 | slow 位置 | fast!=nil && fast.Next!=nil |
|
||
|------|----------|----------|-----------------------------|
|
||
| 开始前 | 2 | 1 | ✅ 继续 |
|
||
| 第 1 轮后 | 3 | 2 | ✅ 继续 |
|
||
| 第 2 轮后 | 1（尾部）| 3 | ✅ 继续 |
|
||
| 第 3 轮后 | nil | 4 | ❌ fast == nil，退出 |
|
||
|
||
**边界规则总结：**
|
||
|
||
| 链表长度 | fast 最终位置 | slow 最终位置 | halfHead（slow.Next）含义 |
|
||
|---------|-------------|-------------|-------------------------|
|
||
| 偶数（如 4） | nil | 第 n/2 个节点 | 后半段起点（第 n/2+1 个） |
|
||
| 奇数（如 5） | nil | 第 (n+1)/2 个 | 跳过中间元素，后半段从第 (n+1)/2+1 个开始 |
|
||
|
||
> [!info] 🧠 为什么 fast=head.Next 比 fast=head 更正确？
|
||
>
|
||
> **问题演示（fast=head 的错误情况）：**
|
||
>
|
||
> 对于单节点链表 `1→nil`：fast=head, slow=head → 不进入循环 → slow=1, halfHead=nil → 对比阶段 p2=nil → 直接返回 true。**正确结果碰巧相同，但逻辑上有隐患。**
|
||
>
|
||
> 对于两节点链表 `1→2→nil`：fast=head, slow=head → 执行一轮 → fast=nil, slow=2 → halfHead=nil → 对比阶段 p2=nil → 直接返回 true。**❌ 错误！应该返回 false。**
|
||
>
|
||
> **原因**：fast=head 时，两节点链表只执行了一轮迭代，slow 直接跳到第二个节点，halfHead 变成 nil，跳过了唯一一次有意义的对比。
|
||
>
|
||
> **修正后（fast=head.Next）：**
|
||
>
|
||
> | 链表 | fast 初始 | slow 初始 | 循环是否执行 | slow 最终 | halfHead | 对比结果 |
|
||
> |------|----------|----------|------------|----------|----------|---------|
|
||
> | `1→nil` | nil | 1 | ❌ | 1 | nil → 直接 return true ✅ | 无需对比 |
|
||
> | `1→2→nil` | 2 | 1 | ❌ fast.Next==nil | 1 | 2 → 对比 1 vs 2 → false ✅ | 正确 |
|
||
> | `1→2→2→1→nil` | 2 | 1 | ✅ × 2 | 2 | 2 → 对比 1==1, 2==2 → true ✅ | 正确 |
|
||
|
||
#### 第二步：反转后半段
|
||
|
||
利用「23-反转链表」中的迭代反转方法，将 `halfHead` 之后的链表原地反转。
|
||
|
||
以 `1→2→2→1` 为例：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph "前半段"
|
||
F["1"] --> S["2"]
|
||
end
|
||
|
||
subgraph "后半段未反转"
|
||
SH["2"] --> L["1"]
|
||
end
|
||
|
||
subgraph "后半段已反转"
|
||
SH2["1"] --> L2["2"]
|
||
end
|
||
|
||
subgraph "对比阶段"
|
||
COMP["1==1 ✅, 2==2 ✅"]
|
||
end
|
||
|
||
F --> S --> SH -.反转.-> SH2 --> L2 --> COMP
|
||
style COMP fill:#4c4,stroke:#333
|
||
```
|
||
|
||
#### 第三步：逐一对比
|
||
|
||
从 `head` 和 `reversedHalf` 同时出发，逐个节点对比 val。
|
||
|
||
> [!question] 💡 什么时候停止对比？
|
||
> 因为 `reversedHalf` 是反转后的后半段，长度最多等于前半段。当 `reversedHalf == nil` 时说明已全部比对完毕。不需要用到原始的后半段尾节点。
|
||
|
||
#### 完整流程图
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
START(["head = 1→2→2→1"]) --> FIND["① 快慢指针找中点"]
|
||
FIND --> MIDDLE["slow → 节点2, halfHead → slow.Next → 节点2"]
|
||
MIDDLE --> REVERSE["② 反转后半段: 2→1 变成 1→2"]
|
||
REVERSE --> COMPARE["③ 逐一对比\np1: 1→2, p2: 1→2"]
|
||
COMPARE --> EQUAL{"全部相等?"}
|
||
EQUAL -->|是| TRUE["返回 true ✓"]
|
||
EQUAL -->|否| FALSE["返回 false ✗"]
|
||
|
||
style TRUE fill:#4c4,stroke:#333
|
||
style FALSE fill:#f99,stroke:#333
|
||
```
|
||
|
||
**时间复杂度：O(n)** — 找中点遍历 n/2 步 + 反转 n/2 步 + 对比 n/2 步 = 总共约 1.5n 步，仍为 O(n)。
|
||
**空间复杂度：O(1)** — 只用了四个指针变量（slow, fast, prev, curr），无额外空间。
|
||
|
||
> [!warning] ⚠️ 细节陷阱
|
||
> 1. **奇数长度链表**：中间元素不属于任何一半，`slow.Next` 作为后半段起点自然跳过了它，无需特殊处理。
|
||
> 2. **单节点链表 `1→nil`**：fast=head.Next=nil → 不进入找中点循环 → slow=1, halfHead=nil → 对比阶段 p2=nil → 直接返回 true ✅。
|
||
> 3. **两个节点的链表 `1→2→nil`**：fast=head.Next=2 → fast.Next=nil → 不进入循环 → slow=1, halfHead=2 → 反转后 reversedHalf=2 → 对比 1 vs 2 → false ✅。**如果错误地用 fast=head，这里会跳过唯一一次有意义的对比，错误返回 true。**
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
### 伪代码模板
|
||
|
||
```
|
||
// ① 找中点 —— 注意 fast 从 head.Next 开始
|
||
slow := head
|
||
fast := head.Next
|
||
for fast != nil && fast.Next != nil {
|
||
slow = slow.Next // 慢指针走一步
|
||
fast = fast.Next.Next // 快指针走两步
|
||
}
|
||
|
||
// 此时 slow 在中点位置，halfHead 是后半段起点
|
||
halfHead := slow.Next
|
||
|
||
// ② 反转后半段（复用反转链表模板）
|
||
prev := nil
|
||
curr := halfHead
|
||
for curr != nil {
|
||
nextTemp := curr.Next
|
||
curr.Next = prev
|
||
prev = curr
|
||
curr = nextTemp
|
||
}
|
||
reversedHalf := prev
|
||
|
||
// ③ 逐一对比
|
||
p1 := head
|
||
p2 := reversedHalf
|
||
for p2 != nil { // 只需遍历较短的后半段即可
|
||
if p1.Val != p2.Val {
|
||
return false
|
||
}
|
||
p1 = p1.Next
|
||
p2 = p2.Next
|
||
}
|
||
return true
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 三步口诀："找、翻、比"
|
||
> 回文链表问题记住 **"找中点 → 反转后半段 → 逐一对比"** 这个固定套路。这类模式还会出现在以下场景中：
|
||
> - 判断回文链表 → 本道题
|
||
> - 重排链表（L₀→Lₙ→L₁→Lₙ₋₁...）→ 同样用这三步，对比后拼接回去
|
||
> - 链表分割（左半部分 / 右半部分）→ 找中点后断开即可
|
||
|
||
> [!tip] 🔑 循环终止条件的选择
|
||
> 对比阶段的循环可以用 `p2 != nil`（遍历短的那段）也可以用 `p1 != nil`（遍历长的）。选短的更高效，因为后半段长度 ≤ 前半段。
|
||
|
||
> [!note] 🐹 Go 中的链表定义
|
||
> LeetCode 的 Go 环境内置如下结构体定义：
|
||
|
||
```go
|
||
type ListNode struct {
|
||
Val int
|
||
Next *ListNode
|
||
}
|
||
```
|
||
|
||
不需要手动定义，直接在解题中使用即可。
|
||
|
||
> [!info] 📊 三种方法对比
|
||
|
||
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|
||
|------|-----------|-----------|------|------|
|
||
| 栈/切片法 | O(n) | O(n) | 最直观，代码最少 | 不满足进阶 O(1) 空间 |
|
||
| **快慢+反转 ⭐** | **O(n)** | **O(1)** | **最优解，面试标配** | 需要注意奇偶长度边界 |
|
||
| 递归法 | O(n) | O(n) | 代码优雅，天然"逆向" | 空间复杂度高 |
|
||
|
||
> [!success] ✅ 相关题目串联
|
||
> - [23-反转链表](./23-反转链表.md) — 本题的核心子程序，必须先掌握
|
||
> - [141-环形链表](./141-环形链表.md) — 同一组快慢指针技术，换了一个应用场景
|
||
> - [143-重排链表](./143-重排链表.md) — 同样的三步套路，只是最后改为"拼接"而非"对比"
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
### 方法一：切片法（O(n) 空间）
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func isPalindrome(head *ListNode) bool {
|
||
// 单节点一定是回文
|
||
if head == nil || head.Next == nil {
|
||
return true
|
||
}
|
||
|
||
// 第一轮：把所有节点的值放入切片
|
||
var vals []int
|
||
for node := head; node != nil; node = node.Next {
|
||
vals = append(vals, node.Val)
|
||
}
|
||
|
||
// 第二轮：双指针对比首尾
|
||
n := len(vals)
|
||
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
|
||
if vals[i] != vals[j] {
|
||
return false
|
||
}
|
||
}
|
||
|
||
return true
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
### 方法二：快慢指针 + 反转后半段 ⭐（最优 O(1) 空间）⭐
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
func isPalindrome(head *ListNode) bool {
|
||
// 边界情况：空链表、单节点
|
||
if head == nil || head.Next == nil {
|
||
return true
|
||
}
|
||
|
||
// ① 快慢指针找中点 —— fast 从 head.Next 开始，正确处理两节点等边界
|
||
slow, fast := head, head.Next
|
||
for fast != nil && fast.Next != nil {
|
||
slow = slow.Next // 慢指针走一步
|
||
fast = fast.Next.Next // 快指针走两步
|
||
}
|
||
|
||
// ② 反转 slow 之后的后半段链表
|
||
halfHead := slow.Next
|
||
var prev *ListNode
|
||
curr := halfHead
|
||
for curr != nil {
|
||
nextTemp := curr.Next
|
||
curr.Next = prev
|
||
prev = curr
|
||
curr = nextTemp
|
||
}
|
||
reversedHalf := prev
|
||
|
||
// ③ 从头节点和反转后的后半段同步对比
|
||
p1, p2 := head, reversedHalf
|
||
for p2 != nil { // 只需遍历较短的后半段
|
||
if p1.Val != p2.Val {
|
||
return false
|
||
}
|
||
p1 = p1.Next
|
||
p2 = p2.Next
|
||
}
|
||
|
||
return true
|
||
}
|
||
```
|
||
|
||
> [!tip] 🔧 可选优化：恢复链表
|
||
> 如果题目要求"不修改原链表"，可以在对比完成后把后半段再反转回去恢复原状。只需再调用一次反转函数（以 `reversedHalf` 为入口），并将 `slow.Next` 重新指向新头部即可。不过 LeetCode 原题不要求恢复，所以这步可以省略。
|
||
|
||
---
|
||
|
||
### 方法三：递归法（进阶理解）
|
||
|
||
> [!question] 💡 一个奇妙的角度
|
||
> 如果用递归来遍历链表，"递"的时候往前走，"归"的时候往回来——这不就是天然的"从后往前遍历"吗？我们可以让左右两个指针分别在"递"和"归"的过程中相遇对比。
|
||
|
||
```go
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* type ListNode struct {
|
||
* Val int
|
||
* Next *ListNode
|
||
* }
|
||
*/
|
||
|
||
var left *ListNode // 包级变量：从左向右移动（递推过程中保持不变量）
|
||
|
||
func isPalindromeRecursive(head *ListNode) bool {
|
||
left = head // 初始化左指针
|
||
return recurseAndCheck(head)
|
||
}
|
||
|
||
func recurseAndCheck(right *ListNode) bool {
|
||
// 基准情况：遇到 nil，回溯到头节点
|
||
if right == nil {
|
||
return true
|
||
}
|
||
|
||
// 递：一直走到链表末尾
|
||
if !recurseAndCheck(right.Next) {
|
||
return false
|
||
}
|
||
|
||
// 归：在回溯路上逐层对比
|
||
if right.Val != left.Val {
|
||
return false
|
||
}
|
||
left = left.Next // 左指针向前移动一位
|
||
|
||
return true
|
||
}
|
||
```
|
||
|
||
**执行轨迹示意（`1→2→2→1`）：**
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph "递"
|
||
D1["recurse(1)"] --> D2["recurse(2)"]
|
||
D2 --> D3["recurse(2)"]
|
||
D3 --> D4["recurse(1)"]
|
||
D4 --> D5["recurse(nil) ← 基准"]
|
||
end
|
||
|
||
subgraph "归"
|
||
G5["return true"] --> G4["right=1, left=1 → ✅ → left→2"]
|
||
G4 --> G3["right=2, left=2 → ✅ → left→2"]
|
||
G3 --> G2["right=2, left=2 → ✅ → left→1"]
|
||
G2 --> G1["right=1, left=1 → ✅ → done"]
|
||
end
|
||
|
||
D1 --> D2 --> D3 --> D4 --> D5
|
||
style D5 fill:#bbf,stroke:#333
|
||
style G1 fill:#4c4,stroke:#333
|
||
```
|
||
|
||
**时间复杂度：O(n)** — 递深度为 n。
|
||
**空间复杂度：O(n)** — 递归栈占用 O(n) 空间。
|
||
|
||
> [!note] 🤔 这种方法的空间复杂度是 O(n)，不如方法二优秀。但它展示了另一种思考路径——递归可以隐式地"倒序"遍历链表，这在其他场景下也很实用。比如判断链表是否回文、反转链表的递归版本等。
|
||
|
||
> [!tip] 🔑 为什么可以用包级变量 left 而不需要参数传递？
|
||
> 因为递归的 "归" 阶段天然就是后进先出（LIFO）的顺序，恰好模拟了从链表尾部向头部的逆序遍历。左指针 left 只需要在每次返回时前进一步，而右指针 right 通过函数的调用栈隐式地保存了每一层的位置信息。这种技巧在其他需要同时正序/逆序遍历链表的场景中也有应用。
|