找到循环链表的入口真的很奇妙

本文转载自微信公众号“bigsai”，作者bigsai。转载本文请联系bigsai公众号。链表是否有环这个问题看似简单，但是在处理的时候需要注意的地方很多。这道题是一道高频度很高的笔试面试题，记忆不牢很容易忘记。纽扣141和荔扣142，小伙伴在某手采访中认识的。判断一个链表是否有环问题描述：给定一个链表，判断链表中是否有环。如果链表中有一个结点可以通过不断跟踪next指针再次到达，那么链表中就存在环路。如果链表中存在循环，则返回true。否则，返回false。你能用O(1)（即常量）内存解决这个问题吗？分析：对于这个问题，如果没有内存空间限制，首先想到的是用hash的方法，用hash存储节点，然后发送Next枚举链表节点：如果发现是在hash中，则表示有环，返回true。如果枚举到最后结束，说明没有环，但这不满足O(1)空间复杂度的要求。我们应该如何处理呢？如果链表的尾部有环，如果后面再枚举一个节点，就会处于闭环中连续循环枚举，那么如何高效判断有环并能快速终止呢？有环路，其实这条路要经过第二、三次才可以说是有环路。一个指针并没有占用太多空间在存储状态下，无法有效判断是否有环（链表可能很长，也可能已经在循环中），我们可以使用fast和slow指针（双指针）。它的核心思想是使用两个指针：快指针（fast）和慢指针（slow）。两者同时从链表头部开始遍历链表，只是两者的速度不同。如果有环，它们最终会在循环链表中相遇。我们实现的时候，快指针（fast）可以一次走两步，慢指针（slow）可以一次走一步。如果有环，则快指针先入环，慢指针后入环。在慢指针到达终点之前，快指针会追上慢指针。如果快慢指针相遇，就说明有环。如果快指针先为null，则表示没有环。具体实现代码为：/***Definitionforsingly-linkedlist.*classListNode{*intval;*ListNodeext;*ListNode(intx){*val=x;*next=null;*}*}*/publicclassSolution{publicbooleanhasCycle(ListNodehead){ListNodefast=head;ListNodeslow=fast;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow)returntrue;}returnfalse;}}改进：找到环的入口给定一个链表，返回链表的第一个开始进入环的节点。如果列表是非循环的，则返回null。为了表示给定列表中的循环，我们使用整数pos来表示列表尾部连接的位置（从0开始索引）。如果pos为-1，则列表中没有循环。请注意，pos仅用于标识环，不会作为参数传递给函数。说明：不允许修改给定的链表。你能用O(1)的空间来解决这个问题吗？这道题比上一道难一点，因为如果链表成环，就需要找入口。分析：如果不考虑内存占用，我肯定会先考虑hash，保存节点然后如果第二次出现就说明有循环，直接返回。实现代码也很简单，走投无路的时候可以用这个方法：/***Definitionforsingly-linkedlist.*classListNode{*intval;*ListNodenext;*ListNode(intx){*val=x;*next=null;*}*}*/publicclassSolution{publicListNodedetectCycle(ListNodehead){intpos=-1;Mapmap=newHashMap();ListNodeteam=head;while(team!=null){if(map.containsKey(team)){pos=map.get(team);returnteam;}elsemap.put(team,++pos);team=team.next;}returnnull;}}但是空间复杂度怎么用O(1)的复杂度来完成这个操作？上题的思路是用速度指针判断是否有环，但是如何锁定环的入口呢？这道题看似算法题，其实是一道数学推理题。这道题的关键也是速度指针，只是需要挖掘更多的细节。回想一下快慢指针能挖掘出的细节：知道慢指针走了x步，快指针走了2x步，但是仅仅知道这两个条件是推不开任何东西的，我们能进行的操作也只有是执行某些操作的O(1)方法。但是，速度指针与之前的不同之处在于，我们使用了一个头节点来开始计数。我们还能做什么？既然我们知道我们相遇的点在环中，我们就可以用一个新的节点来枚举一个圆，看看这个环有多长。哇！在这里，我们可以知道快的步数2x，慢的步数x，环长y。我们知道慢指针是第一次进环，而快指针可能走了好几次，但是多走的步数必须是环的整数倍（否则不可能在同一个位置相遇).则可以得到快指针步数=慢指针步数+n圈的长度。当然这里不知道n是多少。换算成公式，即2x=x+ny消去一个x得到：x=ny。在上图中，我还标注了快速指针移动了整数圈。难点就在这里，我们需要绕过它：快指针的额外x是环长y的整数倍n，慢指针的x也是环长y的整数倍n。那么这个有什么用呢？如果一个节点从起点出发，走到快慢交点，需要x步（n*y步）。这时候，如果某个指针从fast和slow的交点开始，走了循环长度的整数倍，到时候它还是在原来的位置。也就是说，从头节点team1开始走x步，从快慢交集节点team2开始走x步。他们最终还是到达了快慢相交节点，但是在枚举的路上，一旦team1节点遍历到环上，那么就和team2节点重合了，所以一旦相等，就是第一个交点.具体实现还是需要判断是否有环。实现代码为：/***Definitionforsingly-linkedlist.*classListNode{*intval;*ListNodenext;*ListNode(intx){*val=x;*next=null;*}*}*/publicclassSolution{publicListNodedetectCycle(ListNodehead){booleanisloop=false;ListNodefast=newListNode(0);//头指针ListNodeslow=fast;fast.next=head;if(fast.next==null||fast.next.next==null)returnnull;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){isloop=true;break;}}if(!isloop)//如果有无循环returnnull;ListNodeteam=newListNode(-1);//下一个头指针为headteam.next=head;while(team!=fast){team=team.next;fast=fast.next;}returnteam;}至此，这个问题就介绍到这里了。如果您有任何想法，请留言。后面我会继续分享更多的数据结构和算法介绍以及重要的题型。欢迎标记。