描述
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
示例
示例1
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例2
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例3
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
解题思路以及代码
快慢指针,慢指针一次走一步,快指针一次走两步。如果带环一定会在环中相遇,否则快指针会先走到链表的尾部。
为什么快指针每次走两步,慢指针走一步可以?
假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在满指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。文章来源:https://www.toymoban.com/news/detail-428576.html
快指针一次走3步,走4步,…n步行吗?
文章来源地址https://www.toymoban.com/news/detail-428576.html
bool hasCycle(struct ListNode *head) {
struct ListNode *fast,*slow;
fast=slow=head;
while(fast && fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow == fast)
return true;
}
return false;
}
到了这里,关于LeetCode141. 环形链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!