> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/vi.-linked-list/142.-linked-list-cycle-ii.md).

# 142. Linked List Cycle II

![](/files/-LxbjmVXSER-RgtMIFsK)

{% hint style="info" %}
Assume `fast` goes `2k` steps and `slow` goes `k` steps, then they meet. Assume slow goes $$k=s+m$$steps, fast goes $$2k=s+m+ar$$ steps, $$a > b$$ . 

So in math, $$2k=2(s+m)=s+m+ar$$ 

Obviously, $$s+m =nr, s = nr-m$$ 

Assume $$n=1, s = r-m$$ (fast only need to step one round more than 2\*slow)

When `slow = fast`, let `slow` continues moving and `start` move at the same time at the same step until they meet. The steps `start` walks is the circle meeting.
{% endhint %}

{% hint style="danger" %}
Initialize`start = head` and `slow = head`. After they move then compare them.
{% endhint %}

{% tabs %}
{% tab title="Java" %}

```java
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != slow) {
            if(fast == null || fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // find the s = r - m + 1
        // 两个pointer再走r-m步就能在s处相遇
        ListNode start = head;
        while(start != slow.next) {
            start = start.next;
            slow = slow.next;
        }
        return start;
    }
}
```

{% endtab %}

{% tab title="Python" %}

```python
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # edge case
        if head == None:
            return None
        
        # regular case 
        slow = head
        fast = head.next
        
        while slow != fast:
            if fast == None or fast.next == None:
                return None
            slow = slow.next
            fast = fast.next.next
            
        # s+m+br+1 = 2(s+m+ar) -> s=nr+1-m=r-m+1
        # let start meet slow
        start = head
        while start != slow.next:
            start = start.next
            slow = slow.next
            
        return start
```

{% endtab %}
{% endtabs %}