Cycle detection 环的判定

Wiki:Cycle detection

 

判断一个链表是否有环,以及求出环的起点和环的长度。

Tortoise and hare

floyd的环判定算法。

时间复杂度 \(O(n)\) ,空间复杂度 \(O(1)\)

首先两个指针slow,fast同时指向链表起点。

fast一次移动两步,slow一次移动一步,即

slow=slow->next

fast=fast->next->next

如果fast走到了链表末尾,说明没有环,如果两指针相遇,说明存在环。

设链表起点到环起点的距离为m,环的长度为len

因为fast走过的长度是slow的两倍,所以第一次相遇时,fast比slow多走了len,即slow走过的长度为len,fast走过的长度为2*len,由此可求出环的长度len

因为slow第二次到达环起点走的长度为len+m,所以第一次向与会slow再走m就会到达环起点,由此可求出环起点

 

 

 

Example

LeetCode 287 Find the Duplicate Number

题目链接:https://leetcode.com/problems/find-the-duplicate-number/

题意:给出含有n+1个数的数组nums,大小在[1,n]区间内,保证只有一个数是重复的,但可以重复多次,求重复的是哪个数。

 

将数组下标和值建立映射关系,有关系的两个值建立有向边x->num[x],可建成一个有向图。

求重复的数就可以转换为求环的起点。

 

 

 

Categories: ACM