对于一个程序猿来说，数据结构和算法的重要性就不用我多说了吧，算法题已然成了现在大厂笔试面试的重头戏，废话少说，Leetcode 刷起来呀。说起刷 Leetcode，我建议你按 tag 刷，不然只能像无头苍蝇，东一榔头西一棒槌，最后事倍功半 (过来人的惨痛经历)。最近正好在刷 Leetcode 上的链表题，也碰到了一些颇具代表性的题型，正好做个记录，也分享给有需要的小伙伴。
对链表不太熟悉的小伙伴碰到链表问题可能会觉得无从下手，相比数组，链表确实会更加抽象，也需要一定的空间想象力，特别是一些指针戳来戳去，容易把人搞懵。这个时候你不妨拿出纸笔，画个简单的示意图，这对你解决链表问题非常有帮助。本篇文章将以图解的方式介绍三道链表反转的算法题，在 Leetcode 上分别对应简单、中等和困难的难度级别，算是比较有代表性的题型，对于解决链表问题很有参考意义。
1、 Leetcode 206 题 Reverse Linked List （难度：简单）
题目描述如下：
反转链表I题目描述
解法一、迭代反转
先来看示意图，以链表1->2->3->4->5为例：
单链表迭代反转示意图
在遍历链表时，每一次循环只需要做三件事，1. 把当前节点的 next 指针指向其前驱节点；2. 把前驱节点指针指向当前节点；3. 把当前节点指针指向其下一个节点。需要注意的是，我们需要一个变量来暂存当前节点的下一个节点，这里我们用 temp 表示，代码如下
public ListNode reverseList(ListNode head) {
// 前驱节点初始为null
ListNode prev = null;
// 当前节点用cur表示
ListNode cur = head;
// 用temp暂存下一个节点
ListNode temp;
while (cur != null) {
// 获取下一个节点
temp = cur.next;
// 把当前节点的 next 指针指向其前驱节点
cur.next = prev;
// 把前驱节点指针指向当前节点
prev = cur;
// 把当前节点指针指向其下一个节点
cur = temp;
}
// 注意最后返回的是prev
return prev;
}
解法二、递归反转
很多题目用递归都可以写出相当简洁的答案，不过相对于迭代，递归确实没那么好理解。本菜鸡至今也只会用递归解决一些相当基础的题目，比如本题。很多人在面对递归问题时都很容易陷入细节中无法自拔，但是再聪明的脑袋恐怕装不了几层递归栈，所以应该把重点放在子问题和结束条件上。这次先上代码再上图
public ListNode reverseList(ListNode head) {
// 递归终止条件是当前节点为空，或者当前节点的下一个节点为空
// 毫无疑问，在这道题中返回的就是单链表的尾节点
if(head == null || head.next==null) {
return head;
}
// 将当前节点之后的子链表反转任务交给子过程处理,不要陷入细节
// 只需要知道子过程可以完成子链表的反转就够了
ListNode p = reverseList(head.next);
// 经过上面的反转，子链表已经反转完成，接下来要做的就是处理子链表和当前节点的关系
// 下面两步配合示意图理解
head.next.next = head;
// 防止链表循环，需要将head.next置为空
head.next = null;
// 每一层递归函数返回的都是p，也就是初始链表的尾节点
return p;
}
假设链表是 1->2->3->4->5，下面是递归过程示意图。
单链表递归反转示意图
下面再贴一个 Leetcode 本题讨论区的一个热评，希望可以帮助你理解递归过程。
不妨假设链表为1，2，3，4，5。按照递归，当执行reverseList（5）的时候返回了5这个节点，reverseList(4)中的p就是5这个节点，我们看看reverseList（4）接下来执行完之后，5->next = 4, 4->next = null。这时候返回了p这个节点，也就是链表5->4->null，接下来执行reverseList（3），代码解析为4->next = 3,3->next = null，这个时候p就变成了，5->4->3->null, reverseList(2), reverseList(1)依次类推，p就是:5->4->3->2->1->null。
2、Leetcode 92题 Reverse Linked List II （难度：中等）
题目描述如下：
翻转链表II题目描述
解析：本题，还有下一个要介绍的困难级别的题目，算是一种类型题，它们都是要对链表中特定区间中的节点进行操作。面对这种题目，有固定的套路可以帮你简化解题思路，套路如下：
- 给链表添加虚拟头节点 dummy，这样就不需要再单独考虑头节点了，可以省去很多麻烦；
- 找到需要操作的链表区间，区间起始节点用 start 表示，结束节点用 end 表示；
- 对区间上的链表进行操作；
- 将操作后的链表重新接回原链表，这里我们需要另外两个变量，前驱节点 prev 和后继节点 successor。
这样，我们就完成了所有操作，返回 dummy.next 即可，示意图如下
单链表区间反转示意图
然后上代码：
public ListNode reverseBetween(ListNode head, int m, int n) {
// 添加虚拟头节点
ListNode dummy = new ListNode(0);
dummy.next = head;
// 前驱节点
ListNode prev = dummy;
// 反转区间开始节点
ListNode start = head;
// 反转区间结束节点
ListNode end = head;
// 后继节点
ListNode successor;
// 第一个for循环可以找到前驱节点和区间开始节点
for (int i = 1; i < m; i++) {
prev = prev.next;
start = start.next;
end = end.next;
}
// 第二个for循环可以找到区间结束节点
for (int i = m; i < n; i++) {
end = end.next;
}
// 找到后继节点
successor = end.next;
// 至关重要的一步，将反转区间的最后一个节点和原链表断开，否则会造成死循环
end.next = null;
// 将反转后的头节点连在前驱结点后面，这里的 reverseList() 方法直接复用上一题的翻转单链表方法即可
prev.next = reverseList(start);
// 反转后，start变成尾结点，把它和后继结点连接起来
start.next = successor;
return dummy.next;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode temp;
while (cur != null) {
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
3、Leetcode 25题 K 个一组翻转链表（难度：困难）
题目描述如下：
K个一组反转链表题目描述.png
解析：本题与上一题有很大的相似之处，都是对区间上的链表进行操作，不同的是本题需要连续对多个区间进行操作，看似无从下手，其实只比上一题多了个循环的过程，过程如下图所示：
K个一组反转链表示意图
代码如下：
public ListNode reverseKGroup(ListNode head, int k) {
// 添加虚拟头结点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode start = head;
ListNode end = head;
ListNode successor;
while (end != null) {
// 循环k次，确定待反转区间
for (int i = 1; i < k && end != null; i++) {
end = end.next;
}
// end节点为空的话说明待反转节点不足k个，直接返回
if (end == null) {
break;
}
successor = end.next;
//至关重要的一步，将待反转链表的最后一个节点和后续链表断开
end.next = null;
// 进行反转链表操作，并将反转后的链表头结点连接在prev之后
// 这里的 reverseList() 方法直接复用第一题的翻转单链表方法即可
prev.next = reverseList(start);
// start在反转后会变成尾结点，将其与successor连接起来
start.next = successor;
// 以下对各变量重新赋值，然后进行下一次循环
prev = start;
start = successor;
end = successor;
}
return dummy.next;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode temp;
while (cur != null) {
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
4、总结
来来来再总结一下，很多链表题都可以通过添加虚拟头结点来简化解题思路，对于区间操作的情况，可以考虑使用前驱、后继、开始和结束等变量，另外就是要多动笔画画，毕竟眼睛看到的会更加直观。
艾玛终于掰扯完了，这些图真是画得我身心俱疲，就当是做个笔记加深印象吧，也希望可以帮到有需要的小伙伴。
网友评论