# 142-Linked List Cycle II
###### tags: `Medium`
## Question
https://leetcode.com/problems/linked-list-cycle-ii/
## Key
1. 這題真的有點難，上一題是要判斷是否為環，這題是判斷環的起點(list的開頭不一定是環的起點)
2. 第一次相遇判斷代表有環存在，慢指針回到list開頭，快指針則繼續走，第二次相遇就是環的開頭
3. 為什麼?
## Reference
## Solution

ListNode *detectCycle(ListNode *head) {
        if(head == NULL) return head;

        ListNode *fast = head->next;
        ListNode *slow = head;
        while(fast != NULL && fast->next != NULL){
            if(fast == slow){ // 第一次相遇，slow回到head, fast从相遇点下一个节点开始走
                slow = head;
                fast = fast->next;
                while(fast != slow){ // 第二次相遇的地方就是环的入口
                    fast = fast->next;
                    slow = slow->next;
                }
                return slow;
            }
//因為list可能很短，很快就相遇，所以先判斷是否有環，再做位移
            fast = fast->next->next;
            slow = slow->next;
        }

        return NULL;
    }