前言：Hello！大家好，我是@每天都要敲代码，前两期我们已经学习了链表(单链和双链)，没有掌握的同学不妨先去学习一下：单链表和双链表；今天就带大家一起学习一下链表的几个经典例题，巩固一下所学的知识是否能灵活应用！

目录

题目1：翻转链表

思路一：三个指针翻转===》循环迭代

思路二：头插法===》取节点头插到新链表

题目2：链表的中间节点

思路： 双指针===》快慢指针

题目3：合并两个有序链表

思路：利用尾插

代码优化1：

代码优化2：

题目4：判断链表是否有环

思路：双指针法===》快慢指针

扩展两个思考题：

题目5：求环形链表的入口点

思路：画图推导

总结：

题目1：翻转链表

思路一：三个指针翻转===》循环迭代

什么意思呢？就是把指针的方向翻过来；例如：1—>2—>3—>NULL，通过翻转指针我们就会得到NULL<—1<—2<—3，有了简单的思路，下面不妨通过画图分析一波。

逻辑图：

第一步：

 第二步：

第三步： 

第四步： 

具体代码：

根据我们上面的简单分析，我们就可以开始写出核心代码了：

思路二：头插法===》取节点头插到新链表

怎么理解呢？就是取原链表的节点，头插到新链表当中。有了思路，老规矩，我们还是通过画图先分析一波。

逻辑图：

第一步：

 
第二步：

 第三步：

 第四步：

具体代码：

根据我们上面的简单分析，我们就可以开始写出核心代码了：

题目2：链表的中间节点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。例如：

思路： 双指针===》快慢指针

我们不妨定义两个指针：一个慢指针slow，一个快指针fast ，这两个指针的起点是相同的，快指针fast每次都比慢指针slow走快一步。才开始都初始化等于头指针head；slow = head，fast = head；然后每次慢指针走一步：slow = slow->next；快指针走两步：fast = fast->next->next；有了思路我们先画图分析：

逻辑图：

第一种情况：对于偶数个数据

第二种情况：对于奇数个数据

具体代码：

根据我们上面的简单分析，我们就可以开始写出核心代码了：

题目3：合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

思路：利用尾插

我们创建一个新的链表，然后把另外两个链表的数据，每次取最小值，依次尾插进来就可以了；下面画图分析一下：

逻辑图：

第一步：

第二步：

第三步：

第四步：

第五步：

第六步：

第七步： 

具体代码：

根据我们上面的简单分析，我们就可以开始写出核心代码了：

代码优化1：

我们发现上述代码好像有很多类似和冗余的，因为我们并不知道才开始list1和list2谁大谁小，所以我们第一次插入时，都需要判断一下；如果我们先直接取两者最小值作为头，后面不就可以直接插入了吗？避免每次都要在循环里判断一下！

具体代码：

代码优化2：

有了上面的思路，我们不难想出哨兵位作为头，我们开闭一个空间的指针作为头结点；后面的链各个链表插入时，也不需要在做判空的判断，直接插入就可了；最后我们在把创建的哨兵位非free掉就可以啦！

具体代码：

题目4：判断链表是否有环

给你一个链表的头节点 head ，判断链表中是否有环。有环返回true，没环返回false

示例1：

 示例2：

思路：双指针法===》快慢指针

这道题目的思路和题目2的思路很相似，都是采用双指针；一个慢指针flow和一个快指针fast；如果有环，快指针和慢指针会相遇，此时就返回true；如果没环，快指针和慢指针永远不会相遇，此时返回false。下面先画图分析一下：

逻辑图：

第一种情况：如果没有环

第二种情况：如果有环

 具体代码：

根据我们上面的简单分析，我们就可以开始写出核心代码了：

扩展两个思考题：

有了上一题的分析，我们不妨扩展一下，提出两个问题：

1、请证明：slow一次走一步，fast一次走2步；slow和fast一定会在环里面相遇？有没有可能追不上？

2、请证明：slow一次走一步，fast一次走3步行不行？

                   slow一次走一步，fast一次走4步行不行？

结论：

1、slow一次走1步，fast一次走2步，一定能追上

slow进环以后，fast正式开始追了，假设slow和fast之间的距离是N；在追的过程中，他们之间的距离是如何变化的？

距离从N—N-1—N-2—N-3—N-4......—0，每次距离缩小1，最终肯定会使距离缩小到0；距离是0的时候肯定就相遇了！

2、slow一次走1步，fast一次走3步，不一定能追上；甚至可能会死循环，永远追不上

slow进环以后，fast正式开始追了，假设slow和fast之间的距离还是N；在追的过程中，他们之间的距离是如何变化的？

距离从N—N-2—N-4—......最终的距离就不一定是0；有两种可能性：

如果N是偶数那么可以减到0，如果N是奇数那么最终减到-1；

距离是0：代表相遇；

距离是-1：代表fast反超了slow，进入新的追逐，它们的距离变成了C-1（C是环的长度）。如果C-1是偶数，就能追上；如果是C-1是奇数，它们又再次错开，距离还是C-1，陷入死循环，永远追不上！

我们不妨画图理清一下思路：

slow一次走一步，fast一次走4步这里不再赘述，还是要分开讨论，N—N-2—N-4—.....最终的结果就有可能使0、-1、-2；感兴趣的小伙伴可以自己去分析一下!

题目5：求环形链表的入口点

思路：画图推导

这道题的连贯性就比较强，会用到题目2和题目4的知识点！！！有了上面的分析，我们得到只有快指针fast比慢指针slow多走一步，才会必然相遇；在这个条件下，我们不妨求它们的入口点：

 我们不妨设相遇点为meet，先给出结论，然后我们在推导一下这个结论：一个指针从meet点开始走，一个指针从链表开始走，它们会在入口点相遇；我们不妨画图来分析一下：

这里快指针fast的路程为什么是L+nC+x，而不是L+C+X？ 我们不妨考虑这一种情况：

 当L很长时，而C很短时，在slow进环之前，fast可能就不止转了1圈；所以当slow进环后，fast追上slow，fast就可能转了nC圈！

有了上面的分析我们不妨推导一下，我们知道当快指针fast和慢slow相遇时，fast走的距离应该是slow的2倍：

 所以我们前面的结论就推导出来了：一个指针从meet点开始走，一个指针从链表开头开始走，它们会在入口点相遇！！！

具体代码：

根据我们上面的简单分析，我们就可以开始写出核心代码了：

总结：

     以上就是今天学习的的内容，这些题目并没有让我们直接去写链表的一些接口，但利用的都是链表的知识点。我们通过先画图分析的方式，让大家更容易理解！我们只有分析明白了，再写代码实现时，才会更加的顺畅；希望这篇博客让各位有所收获。感谢支持！