【玩转链表②】没做过这几道题目，别再敢说单链表入门了
学习导航
一、前言
🐱💻博主概况: 霉霉铁杆粉、算法爱好者、南邮大一学生
🐱👤参考资料: 《代码随想录》在线资源
🐱💻适用对象：初学链表者或者缺乏链表刷题经验者
🐱🚀专栏宣传：算法入门系列长期更新，欢迎点赞收藏，祝大家学有所获。
本文的重点在于引导大家如何思考和解决问题，而不是具体的代码实现，同时为了减少文章篇幅，本文所有题目的解题代码我都以题解的形式贴在Leetcode或者牛客网上。但是我的能力有限，可能对解题方法的理解有误区，希望大家不吝赐教。
二、基础技法（理论知识）
①哨兵结点法
哨兵结点也可以叫做哑结点后者虚拟结点，顾名思义，哨兵结点是“虚拟”的一个结点，他们是纯功能性的，不存储任何有效的数据，其主要目的是使链表
标准化，如 保证链表永远不为空、永不无头、简化插入和删除 。
不仅在链表中，哨兵结点也广泛应用于树中，如伪头、伪尾、标记等。可能大家光从理论上体会不到哨兵结点的作用，但在接下来的题目分析中相信大家会有所体会
②快慢指针法
快慢指针是双指针法的一种，对于双指针掌握不好的同学可以看看之前的博客[零基础算法入门①] 双指针法。
快慢指针法的实现方式主要有以下两种：
- ①开始时先让fast指针走几步，再让fast和slow指针以相同的“速度”移动
- ②快慢指针同时移动，快指针每次走多步，慢指针少走几步
快慢指针法归结起来适合以下的问题：
- O(n)的时间复杂度内找到 第n个/倒数第n个/中间 结点（方法①）
- 验证链表是否成环以及在寻找入环的第一个结点(方法②)
空有理论是不够的的，我们在接下来的代码实战中感受快慢指针法的魅力。
③做题建议
链表的问题很容易出错，很多时候是因为没有控制好边界，导致对空指针错误的访问。所以我建议大家在做题还不熟练的时候，画出链表的关系图，想清楚边界条件，避免出错。
三、问题分类（代码实战）
①增删查改类设计问题
🌮203. 移除链表元素
「🎯题目呈现」
「传送门：203. 移除链表元素」
「💬题目评析: 难度★☆☆☆☆」
非常基础的题目，要删除某一结点(n)，我们需要找到前一个结点(n-1)，同时要记录下一个结点(n+1)，使得(n-1)结点指向(n+1)结点就实现了删除的效果:
「🔎解题思考」
大家做题时思考以下几个问题：
- 删除的是头结点和尾结点这一类特殊情况怎么处理
- 链表中只有两个结点、一个结点怎么删除
- 连续一串都是待删除的数该怎么处理
显然通过增加判断语句我们都可以解决上面的问题，那有没有什么方法可以实现代码的标准化，而不用搞特殊呢？
「⭐参考题解」
为了实现代码的标准化，我们可以考虑使用哨兵结点。在Leetcode题解里，我贴了使用和不使用哨兵结点的区别，大家可以体悟一下：
【刷爆Leetcode】哨兵结点 VS 不用哨兵结点
🥪707. 设计链表
「🎯题目呈现」
「传送门：707. 设计链表」
「💬题目评析: 难度★★☆☆☆」
大家千万不要被题目长度吓到了，其实本质很简单，就是对单链表增删查改接口的实现，这在我们前一篇博客里做了非常详细的代码讲解，不会的同学请务必先看完上一篇博客【玩转链表①】单链表动图图解（超详解），再试着自己做一遍。大家第一次做设计类的问题可能有些吃力，但做出这么长的题目还是挺有成就感的不是吗🤗
「🔎解题思考」
大家做题时思考这么一个问题：
- 为什么题目示例在调用函数时首先创建一个不含有效值的结点？我们需要对它赋值吗？这个结点有什么用呢？
「⭐参考题解」
我在Leetcode里写了详细的函数分解：【刷爆Leetcode】带头单链表的接口设计
「🚥题目反刍」
相信你做完上面两个题目对哨兵结点的作用有了初步的体会吧，现在我们再来详细说一下哨兵结点的作用
现在我们假设没有哨兵结点，初始只有一个什么都没有的指针NULL。那么在设计插入结点的相关函数前都需要判断传入的头结点是否为空，在创建第一个结点的时候就需要“搞特殊”。而哨兵结点的存在使得创建任何结点都平起平坐，实现了链表创建的
标准化
②链表中的递归与迭代
「🎯题目呈现」
「传送门：反转链表」
「💬题目评析: 难度★★☆☆☆」
如果是第一次接触这个题目话确实会做的比较吃力。关键是想清楚如何实现链表的反转：
- 将结点(n)的下一结点(n+1)存放在next中
- 将结点(n)的next指向前一个结点(n-1)，对于头结点就是NULL。
- 重复上述操作实现全部反转
「⭐参考题解」
迭代法与递归法对比题解：刷爆Leetcode】图解迭代法与递归法
③快慢指针的使用
🥗876. 链表的中间结点
「🎯题目呈现」
「传送门：876. 链表的中间结点」
「💬题目评析: 难度★☆☆☆☆」
朴素的思想是遍历两次链表，第一次记录共有多少个结点，第二次遍历到一半结点数即可得到中间结点了。那有没有遍历一次就可以得到结果的方法呢？快慢指针法就派上了用途，同时我们也用上之前讲解过的哨兵结点：
「⭐参考题解」
从上面我们也可以看到当我们画好图，分清楚情况就可以知道，我们的边界该如何控制【刷爆Leetcode】图解中间结点问题（双指针法）
🥙141. 环形链表
「🎯题目呈现」
「传送门：141. 环形链表」
「💬题目评析: 难度★★☆☆☆」
如何说明链表存在环呢？一个直观的想法是下一个链表节点一直不为NULL，但如果链表很长呢，显然一直遍历不是一个好办法。但在这里快慢指针法可以派上用场。一个环就好比是是一个操场，我们可以这样想，两个人在操场上跑步，只要赛道是一个环，那么跑的快的人一定会追上跑的慢的人，由此类比我们的快慢指针，是不是就有了思路了。
「🔎解题思考」
请大家在做题时思考下面两个问题：
- 判断快慢指针是否相遇可以用 fast→val == slow→val 吗？
- 若慢指针每次走一步，快指针每次走两步。a表示公共路段，紫点表示相遇点。那么请问快慢指针相遇时，慢指针走了的距离是 b 还是 b+ (n圈) 呢？
「⭐参考题解」
直接看官方题解吧😜
「🚥题目反刍」
我们来回答上面两个问题：
1.不可以根据值进行判断，值可能会重复。所以我们直接判断两个指针是否相等
2.慢指针不可能走完一圈！ 我们从初中物理的角度形象说明这个问题。 假设慢指针速度为1，快指针速度为2，所以快指针相对于慢指针的速度为1。那么我们有：
≤号左边表示表示慢指针走完一圈所需要的时间，右边表示脍快指针追上慢指针所用的时间。所以显然在慢指针走完一圈之前快指针就追上了慢指针。最极限的情况是快慢指针同时进入循环。
④小学数学思维在链表中的应用
「🎯题目呈现」
「💬题目评析: 难度★★☆☆☆」
首先我们应该想到使用双指针法在两条链表上开始遍历，但是如何说明开始相交了呢？很简单，只要能说明 p1== p2。如果AB链表相交结点之前的结点数相同，那么p1和p2“顺理成章”的会在c1结点相遇，所以我们需要解决的就是AB节点数不同的情况该怎么处理呢？巧妙的思路是AB前面的结点互补一下：
「⭐参考题解」
【刷爆Leetcode】图解相交问题，一看就懂
四、课后练习
相信大家已经掌握了上面所总结的几种问题，那么是时候做些作业来巩固自己的知识啦。针对上面的每一个问题我都准备了相应的配套练习，虽然难度会更高，但是我会给大家适当的提示。那么刷起来吧！！
练习①：「传送门：19. 删除链表的倒数第 N 个结点」
「💬题目评析: 难度★☆☆☆☆」
🚀 巩固知识点：哨兵结点 + 快慢指针
通过创建哨兵结点，避免对头结点进行特殊的判断。通过快慢指针的第一种方法，实现一次遍历找到倒数第N个结点的前一结点。
练习②：「传送门：21. 合并两个有序链表」
「💬题目评析: 难度★☆☆☆☆」
🚀 巩固知识点：链表中的递归与迭代
分别尝试使用(哨兵节点法 + 迭代)与(递归解法)
「⭐参考题解」
【刷爆Leetcode】递归法与哨兵结点法比较
练习③：「传送门：OR36 链表的回文结构」
「💬题目评析: 难度★★★☆☆」
🚀 巩固知识点：查找中间结点+反转
联想数组，如何验证回文结构呢？我们是不是定义两个指针从后往前遍历，看看值是不是都一样呢？同样的在链表中我们也可以采取这种思路。但是由于单链表不能从后往前遍历，那我们是不是可以考虑将后半部分链表反转呢？
「⭐参考题解」
题解 | #链表的回文结构#C语言详解（对一道会三道）
练习④：「传送门：142. 环形链表 II」
「💬题目评析: 难度★★★★☆」
🚀 巩固知识点：环形链表+数学分析
前面我们学会了如何判断环形链表，那我们如何进一步判定是在哪个部分入环的呢？我们是不是可以联想之前做过 [相交结点的判断]，找出某种存在的数学关系呢？联想之前的速度模型，两个结点的运动时间是一样的，由此列方程。同时注意我们之前提到的slow指针不可能走完一圈的结论。
「⭐参考题解」
官方题解
练习⑤：「传送门：CM11 链表分割」
「💬题目评析: 难度★★★★☆」
🚀 巩固知识点：构建新的结点
在原链表上操作将会异常繁琐，由于链表的查找速度是O(n),所以我们思考能否创建两个链表，分别连接大于target的结点和小于target的结点。
「⭐参考题解」
题解 | #链表分割#C语言思路详解
五、后记
虽然本文已经不贴上代码，可文章字数还是飙到8000+，几乎文中讲到的每一道题目都写了题解，工程量还是蛮大的。学算法又是一个掉头发的事，看在我这么辛苦的份上，点个赞再走吧。下次再见！
