142. Linked List Cycle II

Problem Statement

Linked List Cycle II - LeetCode

Pattern: Pattern Fast and Slow Pointer}

---

Solution

public ListNode detectCycle(ListNode head) {
	ListNode slow = head, fast = head;
	while (fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
		if (slow == fast) break;
	}
	if (fast == null || fast.next == null) return null;
	while (head != slow) {
		head = head.next;
		slow = slow.next;
	}
	return head;
}

Explanation:

continued from

Transclude of GFG-Detect-Loop#why-fast-pointer-skips-1-specifically

How do they meet, and then meet again?

Simply said, when F and S meet at x + y

• Length travelled by S : x+y
• Length travelled by F = 2 (x+y) (cuz it was moving 2x as fast as S)

The difference of Len(F) - Len(S) = x + y = ? (what). lemme rephrase this, How much farther did F travel than S ? rephrased again…

Once F had travelled (x+y) what was it doing waiting for S to catch up? That’s right, going around in circles… of size C. How many times? Who knows 🤷‍♂️, some constant K or N

we got two pointers, and we know the head position of the LL, and the meeting x+y position so now how do we find x ?

Let’s see. S enters the circle and meets with F at y inside the circle. This time, with S at an offset of y let it go around in circles, till head pointer meets up with it, except since we offset it by y, they meet up at x+y - y -> x 🤯