网站流量监测网站注册地址

问题入口

思想：Floyd's Tortoise and Hare 

这个算法简单来说就是设置一个慢指针（一次移动一个位置）和一个快指针（一次移动两个位置）。在遍历过程中，如果慢指针和快指针都指向同一个元素，证明环存在；否则，环不存在。

点击上面这个标题链接，主要是帮助我们理解为什么这两个指针一定会相遇（ps. 即使两个指针起点位置不同依然成立）。

s为慢指针，f为快指针。假设他们之间的距离为10，如下图所示。

 经历一次移动，s会向前走一步，此时距离会变成10+1=11。f向前走两步，此时距离会变成9。

 综上，快慢指针的距离会一次次减少，最终相遇。

class Solution {
public:ListNode *slow, *fast;bool hasCycle(ListNode *head) {slow = head;fast = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if (fast == slow) return true;}return false;}
};

注意fast != NULL && fast -> next != NULL。