- 描述
要求:空间复杂度 O(1),时间复杂度 O(n) 输入分为两部分,第一部分为链表,第二部分代表是否有环,然后将组成的head头结点传入到函数里面。-1代表无环,其它的数字代表有环,这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。 例如输入{3,2,0,-4},1时,对应的链表结构如下图所示: 可以看出环的入口结点为从头结点开始的第1个结点(注:头结点为第0个结点),所以输出true。
- 示例1
- 示例2
- 示例3
- 算法思想
1、设置快慢两个指针,初始都指向链表头。
2、遍历链表,快指针每次走两步,慢指针每次走一步。
3、如果快指针到了链表末尾,说明没有环,因为它每次走两步,所以要验证连续两步是否为NULL。
4、如果链表有环,那快慢双指针会在环内循环,因为快指针每次走两步,因此快指针会在环内追到慢指针,二者相遇就代表有环。
- 代码
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 bool hasCycle(ListNode *head) { 12 ListNode *slow=head; 13 ListNode *fast=head; 14 //使用快慢指针 15 while(fast&&fast->next){ 16 fast=fast->next->next; 17 slow=slow->next; 18 if(fast==slow) 19 return true; 20 } 21 return false; 22 } 23 };
参考:题解 | #判断链表中是否有环#_牛客博客 (nowcoder.net)
标签:结点,判断,ListNode,fast,链表,有环,指针 From: https://www.cnblogs.com/yueshengd/p/17379238.html