给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
思路!
最常见的算法是使用 快慢指针法,也叫龟兔赛跑算法(Floyd's Cycle Detection Algorithm)。这个算法的核心思路是利用两个指针:
- 慢指针 (slow) 每次只移动一步。
- 快指针 (fast) 每次移动两步。
- 如果链表有环,那么快指针和慢指针最终会在环中相遇。如果链表没有环,那么快指针会在链表末端(null)结束。
var hasCycle = function(head) {
if (!head || !head.next){
return false;
}
let fast = head.next;
let slow = head;
while(fast !== slow){
if(!fast || !fast.next){
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
};
✨为什么 fast 要从 head.next 开始
如果 fast 和 slow 都从 head 开始(也就是链表的起点),在进入循环的第一步时,fast 和 slow 可能立刻相等,因为它们都指向同一个节点,即链表的头节点。这种情况下,算法会误判链表是有环的,尽管实际上链表可能没有环。
为了避免这个问题,我们让 fast 指向 head.next,也就是让快慢指针一开始分开一步。这样在进入循环时,快慢指针至少不会在起点相遇,只有当链表真的有环时,fast 才有机会通过它的“快速度”在后续的某个点追上 slow。
适用场景
快慢指针是一种非常高效且常用的链表问题处理方式,除了环形链表和回文链表,还可以应用在:
- 寻找链表的中点。
- 寻找链表的倒数第 k 个节点。
- 判断链表长度的奇偶性。