美文网首页
【LeetCode-141 | 判断链表是否有环】

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

作者: CurryCoder | 来源:发表于2021-12-27 22:13 被阅读0次
    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;
        }
    };
    

    相关文章

      网友评论

          本文标题:【LeetCode-141 | 判断链表是否有环】

          本文链接:https://www.haomeiwen.com/subject/bqquqrtx.html