首页 > 代码库 > 检测链表是否有环,并且找到环的入口
检测链表是否有环,并且找到环的入口
第一步:检测链表是否有环。
方法还是比较多的,这里先讲一个:快慢指针。
快慢指针的方法,就是让两个指针同时指向链表。在向后遍历的时候,一个指针每次走两步,称为快指针;一个指针每次走一步,称为慢指针。如果快慢指针相遇,则说明链表有环,否则无环。(后面证明。)
代码实现如下:
// 如果有环,则返回快慢指针相遇点。如果没环,则返回NULL。positionIsLoop(list l){ if (l == NULL) { printf("Invalid parameter for function IsLoop!\n"); exit(-1); } list fast, slow; fast = slow = l; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) return slow; } return NULL;}
第二步:找到环的入口。
先画张图吧:
这是个有环的链表。
链表开头与环的入口的距离为a,快慢指针相遇的地点距离环的入口为b,环的长度(节点的数量)为c。
那么我们可以知道,当快慢指针相遇的时候,快指针走的路程是慢指针的2倍。如果相遇的时候慢指针在环中走了m圈,快指针在环中已经走了n圈,那么必有n/m >= 2。
所以我们可以知道,相遇时,慢指针走的距离s1是a+mc+b,快指针走的距离s2是a+nc+b。
根据2*s1 = s2,我们有2(a+mc+b) = a+nc+b。
即a = (n-2m)c-b
n-2m是一个非负的常数。
(1)如果n-2m=0,又因为a和b也非负,所以a和b皆为0。意味着相遇点和入口重合,是链表的第一个结点。即环的入口就是链表的第一个结点。
(2)如果n-2m>0,设为N。则a=Nc-b=(N-1)c + c-b,这个式子意味着从链表开头到环的入口的距离,等于从相遇点到入口的距离。而这个结论在(1)中的特殊情况也适用。
如果编程解决的话,就是让两个普通的指针(慢指针),一个指向链表的开头,一个指向相遇点,然后开始往后走,直到它们相遇。而相遇点就是环的入口。
检测链表是否有环,并且找到环的入口
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。