###### tags: `LeetCode` `Medium` `Linked List` `Two Pointer`
# LeetCode #142 [Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/)
### (Medium)

給定一個鏈結串列，返回鏈結串列開始入環的第一個節點。 如果鏈結串列無環，則返回 null。

為了表示給定鏈結串列中的環，我們使用整數 pos 來表示鏈結串列尾連接到鏈結串列中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈結串列中沒有環。注意，pos 僅僅是用於標識環的情況，並不會作為參數傳遞到函數中。

說明：不允許修改給定的鏈結串列。

---
可參考 [#287](https://hackmd.io/gVZKOpAERHCOeZiKW3pExg)

---

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head||!head->next)return nullptr;
        ListNode *f = head, *s = head;
        while(f&&f->next){
            f=f->next->next;
            s=s->next;
            if(f==s)break;
        }
        f=head;
        if(f==s)return f;
        while(f!=s&&s&&f){
            f=f->next;
            s=s->next;
            if(f==s)return s;
        }
        return nullptr;
    }
};