141. 环形链表
3 min
题目
解法：快慢指针
思路
核心思想是快慢指针法（Floyd判圈算法）。快指针每次移动两步，慢指针每次移动一步，若存在环则两指针必会相遇。
正确性基于相对速度：当慢指针进入环时，快指针已在环内且领先若干节点。由于快指针相对慢指针每步靠近1个节点，在有限步内必然相遇。若链表无环，快指针将率先到达尾部终止循环。
- Step 1: 初始化slow和fast指针均指向head
- Step 2: 循环条件：fast非空且fast->next非空
- Step 3: slow移动一步，fast移动两步
- Step 4: 若slow==fast则返回true
- Step 5: 循环结束未相遇则返回false
复杂度
- 时间复杂度: ，最坏情况遍历整个链表（无环时快指针遍历n/2次）
- 空间复杂度: ，仅使用两个指针的常量空间
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL || head->next==NULL){
return false;
}
ListNode *slow = head;
ListNode *fast = head;
while(fast!=NULL && fast->next!=NULL){
slow = slow->next;
fast = fast->next->next;
if(slow==fast){
return true;
}
}
return false;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL || head->next==NULL){
return false;
}
ListNode *slow = head;
ListNode *fast = head;
while(fast!=NULL && fast->next!=NULL){
slow = slow->next;
fast = fast->next->next;
if(slow==fast){
return true;
}
}
return false;
}
};