Algorithm-Day26-Linked-List-Cycle-II-lc142

🧩 Problem Description

Given the head of a linked list, return the node where the cycle begins.
If there is no cycle, return null.

You must not modify the list.

Example:

Input: head = [3,2,0,-4], pos = 1 (tail connects to node at index 1)
Output: Node with value 2

---

💡 Step 1: Detect Cycle Using Two Pointers

Use Floyd’s Cycle Detection (Tortoise and Hare):

• slow moves one step, fast moves two steps.
• If they ever meet, there’s a cycle.
• ✅ Already used in lc-141

---

💡 Step 2: Find Entry Point of the Cycle

✨ Key Insight

Once slow and fast meet:

• Start a new pointer ptr1 from head.
• Start a second pointer ptr2 from where slow and fast met.
• Move both one step at a time.
• They will meet at the cycle entry.

📌 Why it works:
Let:

• L1 = distance from head to cycle start
• L2 = distance from cycle start to meeting point
• C = length of the cycle

Then:
2(L1 + L2) = L1 + L2 + kC ⟹ L1 = kC - L2
So moving L1 from head and L2 from meeting point leads to cycle start.

---

🔢 Java Code

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        // Step 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                // Step 2: Find entry
                ListNode entry = head;
                while (entry != slow) {
                    entry = entry.next;
                    slow = slow.next;
                }
                return entry;
            }
        }

        return null;
    }
}

---

⏱ Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

---

✍️ Summary

• First detect cycle with two pointers.
• Then find the node where cycle begins by moving a new pointer from head.
• No extra memory needed — all in-place.

This is one of the most elegant applications of two-pointer technique in linked lists. Master it!