用动画图解反转链表：三指针法从入门到精通（LeetCode真题演示）

用动画图解反转链表：三指针法从入门到精通（LeetCode真题演示）

链表反转是数据结构与算法中的经典问题，也是技术面试中的高频考点。根据2023年LeetCode用户调研，链表类题目在算法面试中出现概率高达42%，而反转链表及其变种占比超过60%。本文将聚焦三指针迭代法这一核心解法，通过动态图示拆解指针移动过程，并延伸讲解局部反转等变种问题的解决思路。

1. 理解链表反转的本质

链表反转的核心在于改变节点间的指向关系。单链表每个节点只保存下一个节点的地址，反转即让当前节点指向其前驱节点。这一过程需要解决两个关键问题：

1. 指针丢失：直接修改next指针会导致后续节点无法访问
2. 边界处理：头节点和尾节点的特殊处理

提示：链表问题建议先在纸上画出节点和指针关系，再开始编码

三指针法的优势在于：

• 空间效率：O(1)额外空间，优于递归的O(n)调用栈
• 逻辑清晰：三个指针各司其职，适合逐步调试
• 扩展性强：相同思路可解决局部反转等变种问题

2. 三指针法完整拆解

2.1 指针定义与初始化

定义三个关键指针：

• prev：已反转部分的头节点，初始为null
• curr：当前待反转节点，初始为head
• next：保存curr的下一个节点，防止断链

def reverseList(head): prev = None curr = head while curr: next = curr.next # 暂存后继节点 curr.next = prev # 反转指向 prev = curr # 前驱指针后移 curr = next # 当前指针后移 return prev

2.2 单步动画解析

以链表1→2→3→4为例：

1. 初始状态：

   prev = None curr = 1 → 2 → 3 → 4

2. 第一次循环：

   graph LR A[prev:None] B[curr:1] -->|next| C[2] D[next:2]

   执行反转后：

   prev = 1 → None curr = 2 → 3 → 4

3. 第二次循环：

   graph LR A[prev:1] --> None B[curr:2] -->|next| C[3] D[next:3]

   反转后：

   prev = 2 → 1 → None curr = 3 → 4

2.3 常见错误排查

3. 变种问题实战：局部反转

LeetCode 92题要求反转链表中第m到第n个节点。三指针法同样适用：

def reverseBetween(head, m, n): dummy = ListNode(0) dummy.next = head pre = dummy # 移动到反转起始点前 for _ in range(m-1): pre = pre.next # 初始化三指针 curr = pre.next prev = None # 执行局部反转 for _ in range(n-m+1): next = curr.next curr.next = prev prev = curr curr = next # 重新连接链表 pre.next.next = curr pre.next = prev return dummy.next

关键步骤解析：

1. 使用dummy节点处理头节点可能被反转的情况
2. 先定位到反转区间的前驱节点(pre)
3. 标准三指针法执行区间内反转
4. 最后将反转后的子链表重新接入原链表

4. 性能对比与方法选型

实际项目中建议：

• 基础反转：优先选择三指针迭代法
• 复杂操作：如K个一组反转，可结合递归
• 内存敏感：避免递归，选择迭代方案

5. 调试技巧与可视化工具

5.1 纸笔调试法

1. 画出初始链表状态
2. 用不同颜色标注三个指针
3. 逐步执行代码并更新指针位置
4. 特别关注边界条件（空链表、单节点链表）

5.2 在线可视化工具推荐

• Python Tutor：单步执行可视化
• LeetCode Playground：内置链表可视化
• VisuAlgo：交互式算法演示

// 浏览器控制台调试技巧 function printList(head) { let res = []; while(head) { res.push(head.val); head = head.next; } console.log(res.join('→')); }

6. 高频面试考点延伸

面试官常考察的变种问题：

1. K个一组反转：每K个节点作为一组反转
2. 交替反转：如1→2→3→4变为2→1→4→3
3. 回文链表判断：结合快慢指针和反转

以K个一组反转为例的代码框架：

def reverseKGroup(head, k): dummy = ListNode(0) dummy.next = head pre = dummy while True: # 检查剩余节点是否足够k个 last = pre for _ in range(k): last = last.next if not last: return dummy.next # 记录关键节点 curr = pre.next tail = curr # 组内反转 prev = None for _ in range(k): next = curr.next curr.next = prev prev = curr curr = next # 重新连接 pre.next = prev tail.next = curr pre = tail

在准备面试时，建议先掌握基础三指针法，再逐步攻克这些变种问题。实际编码时注意保持指针操作的原子性，每个修改操作都要考虑其对其他指针的影响。