1.jpg
2.jpg
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x): val(x), next(nullptr) {}
};
/*
双指针法: fast and slow
1.快指针fast和慢指针slow同时指向链表头部;
2.遍历整个链表:快指针fast每次移动2步,慢指针slow每次移动1步;
3.当快慢指针可以相遇时,可以证明链表有环否则无环;
*/
class Solution {
public:
bool hasCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) return true;
}
return false;
}
};
