域名解析网站建设重庆万州网站建设公司电话

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中存在环，则返回true。否则，返回false 。

解题思路

采用快慢指针的思想，创建fast和slow一快一慢指针，slow一次走一步，fast一次走两步，如果存在环形结构，那么fast必然先进入环形，slow后进入环形，但是slow早晚也会进入环形，当快慢指针同时进入环形时，假设他们之间的距离差为N，由于slow一次走一步，fast一次走两步，fast每次比slow多走一步，他们之间的距离就会少1，因此，快慢指针必然在环形的某个位置相遇。如果能够相遇，那么必然存在环形结构。如果走着走着，fast指针为空，那么肯定不存在环形结构，因为环形结构不会出现fast为空指针的情况。

实现代码如下：

bool hasCycle(struct ListNode *head) 
{struct ListNode* fast=head;struct ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast == slow)return true;}return false;
}