Skip to content

如何判断一个链表是否有环?

有一次面试有被问到这个问题, 有思路就好

先思考一下,如果存在环,那么当前链表会有什么特点?

存在环就说明链表的尾节点不是指向 null,而是指向了链表中的另一个节点,只有这样才会构成环

知道了链表有环的特点了(这里其实就是特征点),就好办,想办法能探测到这个特征就ok了

解决方法

哈希法 最简单的,很多公司的业务也可以这么做

直接遍历链表,并且判断当前节点是否存在于哈希表中,如果存在,那就说明当前链表存在环,如果不存在,那么我们就将当前链表节点存入哈希表中,并继续往后遍历,直到发生哈希碰撞为止。如果存在环,那么就一定会发生哈希碰撞,如果不存在环,那么就一定有一个节点的 next 指针指向 null,所以循环也会终止。

从处理方法上可以看到以下缺点:

  • 需要申请额外的空间内存储Hash值
  • 最坏的情况下,可以到最后才能检测到,因为是遍历链表

空间复杂度是O(n)

快慢指针法

我们设想一下这么个场景,比如说有两个人在圆形跑道上跑步,一个人一秒钟跑一米,另一个人一秒钟跑两米,然后他们两同时开始并且一直跑,那么他们会不会相遇呢?

答案是只要体力允许,他们两一定会在某一个点相遇;相反,如果是直线跑道,那么他们就不可能相遇。所以我们可以将这个思想利用起来,这就是快慢双指针法。

故一定是圆形,快慢指针才有效

所以很容易得出以下思路: 定义两个指针,一个 slow 指针,一次走一步;另一个 fast 指针,一次走步。如果可以在某一个点满足 slow=fast,那么就说明存在环,否则 fast 指针必然先到到终点。

进阶思考: 如何判断链表中环的位置 | 换种说法,如何找到环的入口位置?

  1. 很简单,如果使用哈希法,冲突的位置就是环的位置
  2. 快慢指针法,这个不行,因为快慢指针相遇的位置不一定是环的位置
那,如何解决呢?

答案是,再引入一个指针.

如果 slow 和 fast 相遇了,那么这时候我们再定义一个指针指向链表起点,一次走一步,slow 指针也同步继续往后走,那么这两个指针就一定会在链表的入口位置相遇。

网站当前构建日期: 2024.07.18