142. Linked List Cycle II
給一個 linked list 的 head，
若是最尾端節點接回中間的某個節點形成環則回傳這個節點，
否則回傳 null。
規定: 不要修改 linked list 上的值
額外挑戰: 只使用 O(1) 的 memory
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation:
https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png
最後一個節點接回 index = pos 的節點 (pos 實際上我們一開始不知道是多少)
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation:
https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation:
只有一個點且沒形成自環
方法一 (space O(N)):
用一個 set 把走過的點存起來，
如果下一個是已經走過的點代表形成環了，回傳這個點，
如果走到末端了還沒遇到任何走過的點代表這個 list 上沒有環。
C++ code:
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
set<ListNode*> st;
st.insert(head);
ListNode *p = head;
while(p){
if(st.find(p->next) != st.end()) return p->next;
st.insert(p->next);
p = p->next;
}
return NULL;
}
};