单链表是否有环，两种方式搞定！
单链表是否有环，两种方式搞定！
微信搜索公众号“兮一昂吧”，点关注不迷路！
背景
数据结构是我们程序员的基本功，无论是在日常工作还是在求职面试中都会经常用到；而且近年来程序员的工作竞争越来越大，数据结构和算法在大厂的面试中都成了必考题。我所了解的：华为技术人员招聘必须先通过机试才能获得面试机会，机试为两道数据结构编码题，每道题200分总分400，240分可通过。字节跳动面试考察算法是出名了的，不必多说。我所经历的美团面试也都考察了数据结构和算法。
由于我们的日常开发工作往往集中在业务逻辑代码的编写，并且运行在Spring等优秀的框架之上，JDK的数据结构虽然熟练使用，但是对于底层逻辑及数据结构的了解少之又少，所以这就导致了面试中的数据结构与算法题目变成了“送命题”。因此，我们开发人员在日常工作中需要多关注这些常用的数据结构、算法，功夫用在平时，多积累，这样在求职时才能够得心应手。
问题
最近有同事到某几个大厂面试，都问到了链表相关的数据结构问题，比如单链表是否有环及环的入口检测问题、单链表元素去重问题、单链表逆置问题等。我研究练习了“单链表是否有环及环的入口检测问题”，作为日常积累，分享给大家。通过下图，了解一下单链表有环和无环的两种情况。
作为链表的第一篇，先看下如何构建链表。简单起见，直接上代码（如下）。为了接下来演示方便，我提供了两种链表的构建方式。第一种方式的目标是根据输入的数组从前往后创建单链表；第二种方式的目标是创建带环的链表，带环的依据是输入的数组序列中有且只有一个重复元素。
/*** 链表节点*/public class Node {public Node(int data) {this.data = data;next = null;}public int data;public Node next;}/*** 构建链表（无环）*/private static Node buildLinklist(int[] texts) {Node head = new Node(0);Node node = head;for (int text : texts) {Node next = new Node(text);node.next = next;node = next;}return head;}/*** 构建链表，可能有环*/private static Node buildCircleLinklist(int[] texts) {Node head = new Node(0);Node node = head;// 存储已经创建过的节点Map<Integer, Node> nodeMap = new HashMap<>();for (int text : texts) {Node next = null;if (nodeMap.containsKey(text)) {next = nodeMap.get(text);} else {next = new Node(text);nodeMap.put(text, next);}node.next = next;node = next;}return head;}
解法一：辅助空间法
单链表是否有环及环的入口检测问题，从题目可以知道，这其实是两个问题。一是：检测单链表中是否存在环；二是：如果存在环，则找到环的入口节点。所以，我们必须先解决第一个问题。
从头节点遍历链表，我们会发现：若链表中存在环，我们将无法找到链表的尾节点，一旦遍历过程进入环，遍历过程将在环内转圈，永远停不下来；若链表中不存在环，在有限的步骤内，我们的遍历过程就会停止。所以，从链表遍历的角度来看，我们可发现链表有环和无环的区别：
•无环：在有限步骤内，我们可以找到链表的尾节点，即：存在一个节点指向空地址。•有环：永远无法找到尾节点，并且会在环内循环。
试想一下：如果我们的遍历过程是有记忆的，记住所有走过的节点（从内存上来看每个节点都是唯一的），那么我们会得出以下结论：
•无环：遍历过程中从头到尾每个节点都是不同的，上图结果为：1-2-3-4-5-6-7-8-9-10-11；•有环：遍历过程中，一旦进入环的循环过程，环内的节点将会重复出现，上图结果为：1-2-3-4-5-6-7-8-9-10-11-4-5-6-7-8-9-10-11-4-5-6……。
所以，我就得出了今天的第一种解法，即：借助辅助空间，存储遍历过程中所有经过的节点唯一信息，每遍历一个节点检查其是否重复出现过，若遍历过程结束也没有发现重复节点，即可说明链表无环；若遍历过程中出现节点重复时，即可说明链表有环，并且第一个重复的元素为环的入口。
补充说明一点：节点唯一信息是通过Node对象的hashCode识别的，对于Node这个类，我并没有重写hashCode()方法，它代表的是对象的内存地址。
具体实现的代码如下所示：
/*** 检查链表中是否有环：采用node唯一信息，配合HashMap** @param head 头节点* @return 若为空，则不存在环；不为空，则输出为入口节点*/private static Node detectCircleByExtraSpace(Node head) {// 用这个map存储所有遍历过的节点Map<Integer, Node> nodeHashCodeMap = new HashMap<>();Node node = head.next;// 节点不空则继续遍历，循环停止的条件有两个：一是遍历到链表尾节点，二是发现重复元素。while (node != null) {// 获取节点hashCodeInteger hashCode = node.hashCode();// 判断是否曾经遍历过if (nodeHashCodeMap.containsKey(hashCode)) {// 如果曾经遍历过，说明有环，并且这是入口return node;}// 遍历过即加入mapnodeHashCodeMap.put(node.hashCode(), node);// 下一个node = node.next;}// 走到这里，就说明没有环了。return null;}
接下来可以写段代码进行测试，下面的例子使用序列“1, 2, 3, 4, 5, 6, 3”创建有环和无环两种链表，结构如下图所示；然后使用detectCircleByExtraSpace进行检测。对于无环的应该输出“无环”，对于有环的应该输出“有环，入口为：3”。
public static void main(String[] args) {int[] texts = {1, 2, 3, 4, 5, 6, 3};Node head = buildCircleLinklist(texts);Node node = detectCircleByExtraSpace(head);printResult(node);head = buildLinklist(texts);node = detectCircleByExtraSpace(head);printResult(node);}private static void printResult(Node node) {if (node == null) {System.out.println("无环");} else {System.out.println("有环，入口为：" + node.data);}}
上面的例子，输出结果如下，符合预期。
有环，入口为：3无环
解法二：快慢指针法
熟悉这道题目的朋友，在看到题目时应该就想到了可以使用快慢指针来解决这个问题。一开始我只能理解检测是否存在环这部分，对于入口检测始终搞不明白，经过一阵公司推导，才弄清楚。这个解法的关键在于如何理解问题，以及理解问题后的一些数学公式推导。我试着说明一下快慢指针的解法原理。
首先看链表环的检测。假如把带环的链表比作一条单向的跑道，只能沿着箭头方向跑，那么跑步的人最终将会在环形跑道内转圈。假设，甲乙两人在沿跑道向相同的方向跑步，其中甲的速度是乙的速度的2倍；那么，甲会先进入环形跑道一直绕圈，乙再进入环形跑道。甲乙都进入环形跑道后，就变成了行程问题中的“追及问题”，由于甲的速度大于乙，那么在一段时间后甲肯定会追上乙的。当然，如果链表中没有环，甲的速度大于乙，那么甲会先跑到终点，过程中不会与乙相遇。
所以，我们可以使用上面“追及问题”的方式来解决链表环的检测问题。设置两个指针fast、slow，从链表头部开始向后遍历，fast的速度是slow的两倍。如果fast能够“追上”slow，则说明链表中存在环；若fast遍历完成走到尾节点，则说明链表中不存在环。
然后分析如何找到环的入口。先说结论：如果链表中存在环，快慢指针相遇后，把fast指针移到链表头部；然后fast和slow以相同的速度（每次移动一个节点）移动，当它们相遇时，相遇的点即为环的入口。再说如何推导，结合下图进行说明：
先做几个假设：
•假设从头节点到环入口的距离为a，从环入口到fast、slow相遇点的距离为b，从相遇点到环入口的距离为c；•再假设链表的长度为L，环的长度为R；•假设slow走的距离为S，那么fast走过的距离为2S（fast除了走过a+b外，可能还会绕环走n圈）。
那么，就会有以下公式的推导：
最终得到：
结合上面说的结论（即：fast、slow相遇后，fast从头节点开始移动，slow从相遇点继续移动，fast的速度与slow一致），仔细看下这个公式代表了什么？
•a代表了从头节点到环入口的距离，相当于fast走过的距离；•c+(n-1)*R代表从slow从相遇点走到环入口后又沿着环走了n-1圈；•以上两者相等即说明：fast、slow会在环的入口相遇；
所以：如果链表中存在环，快慢指针相遇后，把fast指针移到链表头部；然后fast和slow以相同的速度（每次移动一个节点）移动，当它们相遇时，相遇的点即为环的入口。
以上就是快慢指针解法的原理过程，这么看下来其实也是比较容易理解的。但是，如果没有遇到过、听说过，我是真的很难想到这个解法，尤其是第二步查找环入口。好了，理论部分分析完了，我们看下代码该如何实现：
/*** 检测链表是否有环，若有环则找到入口* 使用快慢指针的方式** @param head 链表头节点* @return 若为空，则不存在环；不为空，则输出为入口节点*/private static Node detectCircleByFastSlow(Node head) {// 快慢指针从头节点开始Node fast = head;Node slow = head;// 用于记录相遇点Node encounter = null;// fast一次走两步，所以要保证next和next.next都不为空，为空就说明无环while (fast.next != null && fast.next.next != null) {// fast走两步，slow走一步fast = fast.next.next;slow = slow.next;// fast和slow一样，说明相遇了，或者fast追上slow了。if (fast == slow) {// 记录相遇点，fast或slow都一样encounter = fast;// 相遇了，就退出环检测过程break;}}// 如果encounter为空，说明没有环，就不用继续找环入口了。if (encounter == null) {return encounter;}// fast回到head位置fast = head;// 只要两者不相遇，就一直走下去while (fast != slow) {// fast每次走一步，slow每次走一步，速度一样fast = fast.next;slow = slow.next;}// 相遇点，即为环入口return fast;}
修改上面的测试代码，会发现与解法一的结果一致。
public static void main(String[] args) {int[] texts = {1, 2, 3, 4, 5, 6, 3};Node head = buildCircleLinklist(texts);Node node = detectCircleByFastSlow(head);printResult(node);head = buildLinklist(texts);node = detectCircleByFastSlow(head);printResult(node);}
总结
本文采用“辅助空间法”和“快慢指针法”两种方式解决了判断单链表是否有环及环入口查找的经典问题，两种方法各有利弊，简单总结如下：
•辅助空间法：时间复杂度为O(n)，空间复杂度为O(n)。好处是容易想到，容易理解；坏处是会消耗额外的辅助空间；•快慢指针法：时间复杂度为O(n)，空间复杂度为O(1)。性能较好，但是不容易理解。
数据结构与算法的重要性文章开头已经说了，我还想再补充一些：虽然看起来很难，但是这些常见的问题、解法都是固定的，只要我们多积累、多练习、多思考，并且灵活运用到工作中去，就会发现它其实没有想象中那么难。
如果本文对你有帮助，麻烦转发给更多的朋友看到！