代码优化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点开始走，一个指针从链表开头开始走，它们会在入口点相遇！！！

具体代码：

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

总结：

 

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