【忍者算法】从生活场景理解链表反转：最重要的基础算法｜LeetCode第206题 反转链表

从生活场景理解链表反转：最重要的基础算法

为什么这道题如此重要

反转链表看似简单，却是链表操作的基石。就像建房子要先打好地基，做复杂的链表操作前必须深刻理解反转原理。无数高频面试题都建立在这个基础之上：K个一组反转链表、判断回文链表、链表重排序等等。真正理解了反转链表，这些题目就会迎刃而解。
问题描述

LeetCode第206题"反转链表"要求：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
例如：

1. 输入：1 → 2 → 3 → 4 → 5
2. 输出：5 → 4 → 3 → 2 → 1

复制代码

递归解法：从简单说起

递归法虽然不是最优解，但它的思路最容易理解。想象你在玩多米诺骨牌，先把所有骨牌排好，然后从最后一张开始，一张张往回推。
递归的本质

递归反转的核心思想是：

• 先假设子问题已经解决（后面的链表已经反转完成）
  
• 然后解决当前节点如何与已反转部分衔接的问题
  

就像你要完成一个大项目，不用考虑下属如何完成他们的任务，你只需要考虑如何把大家的工作整合起来。
代码实现和详解

1. public ListNode reverseList(ListNode head) {
2.     // 基准情况：空链表或只有一个节点时，直接返回
3.     if (head == null || head.next == null) {
4.         return head;
5.     }
6.    
7.     // 递归反转子链表，获得新的头节点
8.     // 假设后面的链表已经反转完成，newHead指向反转后的头节点
9.     ListNode newHead = reverseList(head.next);
10.    
11.     // 关键步骤：把当前节点接到反转后链表的末尾
12.     // 假设当前是节点2，head.next是节点3
13.     // head.next.next = head 就是让3指向2
14.     head.next.next = head;
15.     head.next = null;  // 断开2原来的指向，防止形成环
16.    
17.     return newHead;
18. }

复制代码

迭代解法：追求空间最优

迭代法虽然理解起来较难，但它是空间复杂度最优的解法。让我们通过一个生活场景来深入理解。
通过生活场景理解迭代

想象你是一个体操教练，正在教一排学生做"后滚翻"。每个学生原本都面向前方，你要让他们一个接一个地转身。关键是：每处理一个学生时，要确保：

• 这个学生不会摔倒（保存next指针）
  
• 他能拉住前一个学生的手（指向prev）
  
• 准备好扶住下一个学生（移动指针）
  

代码实现和图解

1. public ListNode reverseList(ListNode head) {
2.     ListNode prev = null;   // 已翻转部分的头节点
3.     ListNode curr = head;   // 当前正在处理的节点
4.    
5.     while (curr != null) {
6.         // 第1步：记住下一个学生，以免等下找不到他
7.         ListNode nextTemp = curr.next;
8.         
9.         // 第2步：让当前学生转身（改变指针指向）
10.         curr.next = prev;
11.         
12.         // 第3步：教练和助教往后移动一位
13.         prev = curr;     // prev是"助教"，扶着已完成转身的学生
14.         curr = nextTemp; // curr是"教练"，去帮助下一个学生
15.     }
16.    
17.     return prev;  // prev指向最后一个处理的节点，即新的头节点
18. }

复制代码

迭代法的过程图解

以1→2→3→4→5为例：

1. 初始状态：
2. prev = null, curr = 1
3. null ← 1 → 2 → 3 → 4 → 5
5. 第一次迭代后：
6. prev = 1, curr = 2
7. null ← 1    2 → 3 → 4 → 5
9. 第二次迭代后：
10. prev = 2, curr = 3
11. null ← 1 ← 2    3 → 4 → 5
13. 最终状态：
14. null ← 1 ← 2 ← 3 ← 4 ← 5

复制代码

深入理解的关键点

1. 指针操作的本质

每次操作都是在改变一个节点的"指向"。就像改变一个人的视线方向，原本看着前方，现在要回头看。
2. 迭代法的不变量

在任何时刻：

• prev指向的是已完成反转的部分
  
• curr指向正在处理的节点
  
• nextTemp保存着待处理的部分
  

3. 为什么需要三个指针

• prev：没有它，就不知道往哪里指
  
• curr：没有它，就不知道现在处理谁
  
• nextTemp：没有它，就会断链找不到后续节点
  

实战应用

这个基础算法在很多场景中都有应用：

• 需要倒序处理链表时
  
• 需要判断链表是否回文时
  
• 需要按组反转链表时
  
• 需要重排链表时
  

小结

掌握链表反转需要：

• 理解递归和迭代两种思路的本质
  
• 深入理解指针操作的含义
  
• 反复练习直至形成肌肉记忆
  
• 学会用生活场景类比，加深理解
  

建议：每天默写一遍这道题，直到闭着眼睛也能写对。因为它是链表操作中最基础也是最关键的操作，掌握了它，其他链表问题都会变得容易很多！
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！