【c++&Leetcode】141. Linked List Cycle

问题入口

思想：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。