[数据结构与算法]判断链表中是否有环---CPP实现

描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

思路：

可以使用快慢指针遍历链表。如果链表中存在环，则快慢指针最总会相遇，出现 “快指针==慢指针” 的情况。如果没有，可以设置控制条件：当快指针不为nullptr 或 快指针的next为空时返回，表示链表中没有环。

代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* Slow{head};
        ListNode* Fast{head};
        while(Fast!=nullptr && Fast->next!=nullptr)
        {
            Slow=Slow->next;
            Fast=Fast->next->next;
            if(Slow==Fast)
            {
                return true;
            }
        }
        return false;
    }
};

缺陷：

如果有环，为了达成Fast == Slow条件，存在额外开销。