給定一個鏈表，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。
說明：不允許修改給定的鏈表。
進階：
你是否可以不用額外空間解決此題？
leetcode 最長公共子序列，?
?
方法一：使用map
方法二：
分兩個步驟，首先通過快慢指針的方法判斷鏈表是否有環；如果有環，則尋找入環的第一個節點。具體的方法為，首先假定鏈表起點到入環的第一個節點A的長度為a，到快慢指針相遇的節點B的長度為（a + b）。現在我們想知道a的值，注意到快指針p2始終是慢指針p走過長度的2倍，所以慢指針p從B繼續走（a + b）又能回到B點，如果只走a個長度就能回到節點A。但是a的值是不知道的，注意到起點到A的長度是a，那么可以用一個從起點開始的新指針q和從節點B開始的慢指針p同步走，相遇的地方必然是入環的第一個節點A。?
leetcode約瑟夫環？?
?
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == NULL)return NULL;ListNode *fast = head;ListNode *slow = head;bool haveCycle = false;while(slow ->next != NULL && fast ->next != NULL && fast ->next ->next != NULL){slow = slow ->next;fast = fast ->next ->next;if(slow == fast){haveCycle = true;break;}}if(haveCycle){ListNode *node = head;while(node != slow){node = node ->next;slow = slow ->next;}return node;}elsereturn NULL;}
};
