# 0142. Linked List Cycle II
###### tags: `Leetcode` `Medium` `Cycle`
Link: https://leetcode.com/problems/linked-list-cycle-ii/
## 思路
### 思路一 $O(N)$ $O(N)$
用HashSet记录所有visited过的node，第一个重复的就是cycle的开始
### 思路二 $O(N)$ $O(1)$
参考[这里](https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation.)
数学推导
当fast runner和slow runner都从起点开始跑，假设他们相遇在p点时，fast runner跑了a+k(b+c)+b, slow runner跑了a+b，所以a+k(b+c)+b = 2(a+b) => a+(k+1)b+kc = 2a+2b => (k-1)b+kc = a，因此如果这时slow runner2从起点开始跑 slow runner1从p点开始跑，他们一定会在q点相遇，也就是cycle起点
## Code
### 思路一

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        while(head!=null){
            if(visited.contains(head)) return head;
            visited.add(head);
            head = head.next;
        }
        return null;
    }
}

### 思路二

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode slow2 = head;
                while(slow2!=slow){
                    slow2 = slow2.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}