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;
}
};