一、前言

4月份报名参加了极客时间举办的第一期「算法训练营」，两天线下大课，一个月线上课。

在做线上课程作业的过程中，做了一些总结，在这里分享一下，希望能够帮助到需要的同学，也方便自己以后复习。

那废话不多说，上正文啦。

---

二、链表基本操作

链表这种数据结构本身并不复杂，题型/题量也都不是很多（leetcode打了“链表”标签的题目共计35道）。

而这些题无论再怎么变，一般都跑不了以下这些基本操作：

1. 插入节点，包括头节点前插入、指定节点后插入、链表尾插入等。
2. 删除节点，包括删除头结点、删除指定中间节点、删除尾节点等。
3. 遍历/查找，虽然看起来这好像是句废话，但还是要说一下，因为有些题目确实既不需要插入也不需要删除。

说到这里，你可能会想到另一个常常出现的链表操作：交换节点。

是的，交换节点也是常常遇到的链表操作之一，但其实它可以看做是删除+插入的组合操作。

我们直接上图：

交换节点

「2和3交换」这个操作，完全可以转换为「删除3」+「将3插入到2前面」。

这样一来，交换节点操作也变得更容易理解啦。

---

三、常见题型和解题思路

接下来，我们看看基于这些基本操作，链表题能怎么玩。

我把链表题型做了个“非典型”的分类：常规、进阶和其他。

3.1 常规题

先说第一类：常规题，是指一般不需要其他数据结构辅助进行解题的题型。

这类题相对比较简单，能“变形”的空间也不大，举几个例子~

3.1.1 反转链表

参考 leetcode 第 206 题。

常用解题思路是，从头到尾遍历链表，过程中把遍历到的节点从原始链表头上删除，再插入到新链表的头结点前面。像这样：

反转链表

非常简单对吧？

那我们稍微变形一下：反转前k个节点怎么做？

3.1.2 反转前k个节点

也不难，加个计数器就行了，计数结束则停止反转，然后把两个链表链到一起。

反转链表前k个节点

那在此基础之上，我们再看看两两反转怎么做呢？

3.1.3 两两反转

参考 leetcode 第 24 题。

这里可以参考第一部分交换节点的操作，每次选取两个节点，这两个节点进行交换操作（就是我们前面提到的那样），如图：

两两反转

图画的有点挫，但应该并不难懂，同一个颜色表示一个独立的原子操作。

具体实现时，注意一下每次迭代前看看是不是还有两个节点能构成一组就可以了。

那还有别的思路嘛？

有，我们刚刚说的「反转前k个节点」这时就派上用场啦。

针对当前题目，我们可以假设有两个链表 A 和 B ， A 初始只有一个哨兵节点，B 初始是待反转链表，然后进行多次迭代，每次迭代将 B 的前两个节点拆下来，反转构成新链表，再追加到 A 链表尾，如图：

反转前k个节点

当 B 内节点不足2个的时候，则迭代结束，然后将 B 剩余节点追加到 A 链表尾就可以了。

最终结果就是 A 的哨兵节点指向的链表。

再继续延伸一下，k个一组反转怎么做呢？

3.1.3 k个一组反转

参考 leetcode 第 25 题。

你是不是能够从前面的题目中借鉴思路啦？

还是用两两反转的第二个思路，将题目转换成：

• 两个链表 A 和 B ， A 初始只有一个哨兵节点， B 初始是待反转链表。
• 多次迭代，每次迭代时，将 B 中前 k 个节点反转成为新链表，插入 A 链表尾。
• B 不足 k 个节点时，迭代结束，剩下的 B 插入到 A 链表尾。
• 最终，A 的哨兵节点指向的链表即为所求。

图略，和前面两两反转的类似。

多说一句，像这样的“问题拆解”，能帮我们很好的将复杂问题简化，如果上来就生转的话，较大概率会出错，比如部分成环，debug起来就比较麻烦。

3.1.4 删除有序链表中的重复元素

参考 leetcode 第 83 题。

这道题有多种解法，但不管怎么做最终都是找到值相等的一组连续节点，保留一个，删除其他。如图：

删除有序链表中的重复元素

具体实现上，可以用递归，也可以用非递归；可以每次只删一个，也可以每次删多个。

PS：这道题我开始只写了一种解法，后来 review 其他同学的代码，收获颇多，感恩~~

3.1.5 找到链表的中间节点

参考 leetcode 第 876 题。

大家都知道怎么做啦，快慢指针，快指针步数=慢指针步数*2，慢指针步数=1，快指针走到尾的时候，慢指针就走到了中间位置。如图：

找到链表的中间节点

那么问题来了，换个节点找要怎么做呢？比如，如何找到链表的倒数第n个节点？

3.1.6 找到链表的倒数第n个节点

参考 leetcode 第 19 题。

还是可以用快慢指针，快指针比慢指针先走n步，然后再一起走，快指针到结尾的时候，慢指针指向的就是倒数第n个节点啦。

找到链表的倒数第n个节点

当然这道题还有别的思路，我们后面再讲。

3.1.7 合并两个有序链表

参考 leetcode 第 21 题。

还是删除+插入，只是多了个选大小节点的比较操作，比较简单，不讲啦。

3.1.8 小结

上述这些题都是非常经典的题目，基于这些题型，还可以有更多的变形题或进阶题，感兴趣的小伙伴有时间可以继续挖掘一下~~

如果你对链表的基本操作非常熟悉，那么将这些问题进行拆解后再做就不是很困难啦。

3.2 进阶题

进阶题是指需要用其他简单数据结构（数组、栈、哈希表等）进行辅助解题的题型。还是举几个例子来看看~

3.2.1 链表是否有环/查找链表入环节点

参考 leetcode 第 141 和 142 题。

这道题网上大部分题解都会用快慢指针。

但其实可以结合哈希表做，每一个遍历到的节点入哈希表，若某次入的时候发现哈希表里已经有这个元素了，则链表有环，且当前节点就是入环节点。

3.2.2 回文链表

参考 leetcode 第 234 题。

这道题也有多种解法，可以快慢指针+部分反转来做，也可以用快慢指针+栈来做。

我们这里讲讲第二种解法：
大体思路是，快慢指针遍历链表，链表前半部分元素入栈，链表后半部分与栈顶元素比较，相同则出栈，不同则表示不是回文结构；直到栈空为止，若所有元素都匹配，则说明是回文结构。

回文链表

PS：我在图中只画了链表节点数为偶数的情况，奇数情况下的中间节点要记得做特殊处理哦~

3.2.3 前k个高频词

参考 leetcode 第 692 题。

这道题目没有打“链表”标签，但其中一种解题方法会需要链表+哈希表来保存数据。

思路是先统计词频，再按词频把相同词频的单词用字典序链在一起。

前k个高频词

链表在这里的作用是，字典序保存词频相同的字符串。

当然，这道题也有其他的解法，由于和链表关系不大，这里不细聊啦。

3.2.4 小结

对进阶题型，解题核心思路是：根据题目特性，选合适的数据结构进行辅助。剩下的就是工作量的事儿了。

3.3 其他

剩下的题型，其实也可以算到前两类里面去，但有一些解法比较好（bian）玩（tai），所以单独拎出来聊一聊。比如~

3.3.1 找到链表的倒数第n个节点

参考 leetcode 第 19 题。

前面我们讲了快慢指针的思路，这里讲讲其他的解法。

首先，假设链表长度为 len，则倒数第n个节点前有 len-n 个节点，即：

找到链表倒数第n个节点-分析

在拿到题目的时候，我们只知道 n 的值，而不知道 len 的值。

那么我们只需要第一次遍历算出 len，再进行第二次遍历走 len-n 个节点，就找到倒数第n个节点啦。

找到链表倒数第n个节点-计数法1

如果没有快慢指针的基础，相信大部分人可能都会想到这个解法。

还有另一个思路，有点意思。

• 设 k=n，第一次遍历做 k--，则第一次遍历结束时，k=n-len；
• 第二次遍历做k++，当k=0时，正好走完倒数第n个节点前的 len-n 个节点，于是就找到了倒数第n个节点。

找到链表倒数第n个节点-计数法2

当然，这个解法没有任何时间或空间上的优化，大家看看就好~

3.3.2 相交链表

参考 leetcode 第 160 题。

常规解法，可以用哈希表辅助，不多介绍。
但如果题目对空间复杂度有要求，哈希表就搞不定啦。
怎么办呢？

相交链表-例子

你会发现，当两个链表长度一样的时候，做起来就非常容易了，我们可以同时遍历两个链表，相交节点就是它们第一个相同节点。

这就是关键！对于长度不一样的，先把长的那部分多出来的节点走完就好了，也就是：

相交链表-分析

这样一来，我们可以通过两次遍历完成该题：

• 第一次遍历，统计两个链表的长度；
• 第二次遍历，长链表走到与短链表齐平位置；然后一起往后走，若遇到相同节点，则相交，否则不相交。

3.3.3 复制带随机指针的链表

参考 leetcode 第 138 题。

常规解法，仍然可以用哈希表辅助。
我们假设原链表为A，新链表为B。则可以先为A中的节点逐个做节点拷贝，然后用一个哈希表做A到B的映射。

复制带随机指针的链表-解法1

PS：图中上面的是A（原始链表），下面的是B。

接下来，由于节点已经就绪，A和B之间的节点一对一映射，那么只需要遍历一遍，把每个节点的next指针和random指针指向正确的位置就可以了。

复制带随机指针的链表-解法1

提一下难度，如果题目要求空间复杂度为O(1)怎么办呢？

是不是不用哈希表，遍历A的时候直接完整复制B就可以了呢？

也不是不可以，但问题是，这个链表比较特殊，random指针有可能指向它前面的某一个节点，也可能指向后面的某个节点，如果是后者的话，就没办法提前关联啦。如图：

复制带随机指针的链表-解法2-分析

所以，如果用这种一边遍历A一边生成B的方式来做复制的话，只能先复制 next 链，然后再复制 random链。

然后新的问题又来了，由于A和B的节点之间没有映射关系，A中某个节点的random到B上完全没办法O(1)时间复杂度内找到，只能从头遍历，按位移量找。如图：

复制带随机指针的链表-解法2

只是如此一来，复杂度就比较高了。

一个比较有意思的改进思路是：既然B和A关联不上导致了这些问题，那想办法关联上不就得了。

怎么关联呢？

原地复制，插入原链表中。

复制带随机指针的链表-解法3

这样，我们就可以比较方便的复制 random 指针了。因为每一个被复制的节点，都直接挂在原节点后面，我们完全可以O(1)时间内找到。

复制带随机指针的链表-解法3

最后再把复制节点从原链表中拆出来就万事大吉。

复制带随机指针的链表-解法3

这类题还有很多，我就不一一列举啦，感兴趣的小伙伴们可以继续去探索，相信会有不少收获。

---

四、小tips

在写链表题的时候，有一些小技巧，可以在实现时注意一下：

1. 不要丢节点，有些操作的前后顺序很重要，一不小心把整条链弄丢就糟糕了。
2. 尽可能让你的链表“无环”，即便是临时成环后面再拆解也不行，因为一旦出了问题，排查起来会比较困难。
3. 正确使用哨兵节点，有时它会帮你简化操作。

还有一些小心得，也分享给大家：

1. 同一类型的题目，可以从 easy 开始做，然后到 middle 最后再到 hard，层层递进，因为难题都是由简单题目演进而来的，由浅入深会比较容易接受。
2. 做题前，先对“已知信息”做收集，然后再看利用已有知识，如何达到题目要求。
3. 解题思路可以靠画图辅助梳理，解法也可以在纸上走一遍进行推导，不要上来就写代码。
4. 如果有些题目实在不会解，不要着急看别人的代码，找找相关题型或题目的「题解」，看看别人怎么想的，按照他们的思路走一遭，然后自己再做实现，会比直接看答案更有效果。
5. 最后，同一题可以尝试用不同的方法去解决，如果你已经用一种解法解出来了，想不出更多的解法，那就可以放心大胆的去 review 别人的代码啦，没准儿能有意外收获呢。

---

五、附录

最后的最后，应整理了一些链表题目的具体实现，欢迎感兴趣的同学前来review~

• 21.合并两个有序链表：https://paste.ubuntu.com/p/gpK9CxHh5J/

• 160.相交链表：https://paste.ubuntu.com/p/rkqjSzJpyX/

• 876.链表的中间节点：https://paste.ubuntu.com/p/vH8r5pK7zX/

• 206.反转链表：https://paste.ubuntu.com/p/hBPDddZxvX/

• 83.删除有序链表中的重复元素：

  • 解法1-非递归一次删一组：https://paste.ubuntu.com/p/cNftRJ3tdZ/

  • 解法2-非递归一次删一个：https://paste.ubuntu.com/p/sPC9n8V9mq/

  • 解法3-递归：https://paste.ubuntu.com/p/jPmvhQdDqn/

• 19.删除链表的倒数第n个节点：

  • 解法1-快慢指针：https://paste.ubuntu.com/p/cN2vfzKTgB/

  • 解法2-计数法：https://paste.ubuntu.com/p/sXXmHPhJ6Q/

• 24.两两交换链表中的节点：

  • 解法1-四个临时指针：https://paste.ubuntu.com/p/WxhW26VXzH/

  • 解法2-递归：https://paste.ubuntu.com/p/RKykshJyc7/

• 25.k个一组反转链表：

  • 解法1-非递归：https://paste.ubuntu.com/p/XcyYVTrJRB/

  • 解法2-递归：https://paste.ubuntu.com/p/QbRKg5cbpq/