【LeetCode-141 | 判断链表是否有环】

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;
    }
};