LeetCode-Linked List Cycle II

題目：LeetCode-Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:

Can you solve it without using extra space?

解釋：

做了1就忍不住要做2，這道題要求高了一點。要傳回開始循環的節點，那麼你肯定得找到這個節點。怎麼找？循環連結清單中，有且隻有兩個節點的指針域是相同的，并且相同的兩個指針就是指向循環開始的節點的，是以可以根據這一點來尋找循環連結清單的開始節點。

要實作這個要求，有一個比較直接的方法，即逐個比較法。就是用兩個指針，一個在循環部分不斷的循環（指針 fast），一個從連結清單的頭指針開始移動（指針slow），slow每移動一次，fast 移動一圈，依次比較他們是否相同（雖然感覺這樣的時間負責度會很大，但這總比不做好吧）。實作代碼如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow, *fast;
        ListNode  *p = NULL;
        slow = fast = head;
        while()
        {
            if(fast == NULL || fast->next == NULL )
                return NULL;
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                p = slow;  //記錄目前節點，作是否循環一圈的判斷
                slow = head;
                while()
                {
                    if(slow == fast) return slow;
                    fast = fast->next;
                    if(fast == p)
                    {
                        slow = slow->next; //當fast回到P處
                        //時，即循環完了一圈，此時slow移動一位.      
                    }
                }
            }
        }

    }
};
           

運作，程式通過，不過果然，運作時間72Ms，離系統記錄的12Ms還差很多，這時就要改進代碼了。

再仔細觀察一下循環連結清單的特點，發現在一個循環連結清單中，快慢指針相遇的點總是固定的某點，如圖中的3處，因為快指針一定要比慢指針快了一圈，它們才有可能相遇。再假設它們是完全循環連結清單，那麼它們相遇點肯定是第一個節點，那麼非完全循環連結清單為什麼不是相遇在開始的節點處呢？因為它事先跑了一段無關的路了呀（圖中的1~2段），也正是因為它們跑了一段路了，是以相當于它們在3處開始移動的，也就是說明了什麼？說明1~2段和2~3段的路程是相同的！！是以一個指針從鍊頭開始，一個指針從相遇處開始，同步移動，它們必然會在循環開始處相遇，這樣也就找出來題求的節點了。

代碼如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow, *fast;
        ListNode  *p = NULL;
        slow = fast = head;
        while()
        {
            if(fast == NULL || fast->next == NULL )
                return NULL;
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                slow  = head;
                while()
                {
                    if(slow == fast) return slow;
                    slow = slow->next;
                    fast = fast->next;
                }
            }
        }

    }
};
           

運作用時12Ms。這是完全自己寫的代碼，還沒看大神們的代碼，不知是否相同。雖然思考這道題時用了不少時間，但看到自己的代碼被access時，覺得還是值得的。