如何判断一个链表是否有环?
有一次面试有被问到这个问题, 有思路就好
先思考一下,如果存在环,那么当前链表会有什么特点?
存在环就说明链表的尾节点不是指向 null,而是指向了链表中的另一个节点,只有这样才会构成环
知道了链表有环的特点了(这里其实就是特征点),就好办,想办法能探测到这个特征就ok了
解决方法
哈希法 最简单的,很多公司的业务也可以这么做
直接遍历链表,并且判断当前节点是否存在于哈希表中,如果存在,那就说明当前链表存在环,如果不存在,那么我们就将当前链表节点存入哈希表中,并继续往后遍历,直到发生哈希碰撞为止。如果存在环,那么就一定会发生哈希碰撞,如果不存在环,那么就一定有一个节点的 next 指针指向 null,所以循环也会终止。
从处理方法上可以看到以下缺点:
- 需要申请额外的空间内存储Hash值
- 最坏的情况下,可以到最后才能检测到,因为是遍历链表
空间复杂度是O(n)
快慢指针法
我们设想一下这么个场景,比如说有两个人在圆形跑道上跑步,一个人一秒钟跑一米,另一个人一秒钟跑两米,然后他们两同时开始并且一直跑,那么他们会不会相遇呢?
答案是只要体力允许,他们两一定会在某一个点相遇;相反,如果是直线跑道,那么他们就不可能相遇。所以我们可以将这个思想利用起来,这就是快慢双指针法。
故一定是圆形,快慢指针才有效
所以很容易得出以下思路: 定义两个指针,一个 slow 指针,一次走一步;另一个 fast 指针,一次走两步。如果可以在某一个点满足 slow=fast,那么就说明存在环,否则 fast 指针必然先到到终点。
进阶思考: 如何判断链表中环的位置 | 换种说法,如何找到环的入口位置?
- 很简单,如果使用哈希法,冲突的位置就是环的位置
- 快慢指针法,这个不行,因为快慢指针相遇的位置不一定是环的位置
那,如何解决呢?
答案是,再引入一个指针.
如果 slow 和 fast 相遇了,那么这时候我们再定义一个指针指向链表起点,一次走一步,slow 指针也同步继续往后走,那么这两个指针就一定会在链表的入口位置相遇。
网站当前构建日期: 2024.11.04