題目

今天有一個 Linked list，給你linked list的head node，要判斷此Linked list是否有循環。
循環為true，不循環為false。

解析

這題跟昨天不快樂的人寫了快樂數字的解決方法是一樣! 所以今天介紹一下另外一個演算法
大家還記得昨天的龜兔賽跑演算法(Floyd Cycle Detection Algorithm)嗎? 兔子走比較快，烏龜走比較慢，兔子會慢慢追上烏龜而找到循環點和循環長度。
我畫的很辛苦，所以讓大家再欣賞一次。

Brent's Algorithm

此想法和龜兔賽跑一樣，不一樣的地方在於我們的烏龜進化了!!!變成了忍者龜。
所以只有兔子會往前移動，但每一個移動週期，我們的烏龜會發動忍法，瞬間到兔子的旁邊，然後會把此週期變大。
當兔子移動到循環中，烏龜發動忍法也會進去循環，然後兔子會隨著移動週期變大，而追上烏龜!

Code

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL){
            return false;
        }
        
        ListNode* rabbit = head->next;
        ListNode* turtle = head;
        
        int counter = 1, period = 1;

        while(rabbit != turtle){
            if(counter == period){
                turtle = rabbit; //烏龜發動忍法
                period *= 2;  //週期變大
                counter = 0;
            }
            if(rabbit==NULL){
                return false;
            }
            
            rabbit = rabbit->next; //兔子向前跑
            counter++; 
        }
        return true;
    }
};