In the previous challenge, we learned how to tell if we were stuck in a loop. But in LeetCode 142 (Linked List Cycle II), simply knowing you’re in a circle isn’t enough. The interviewer wants to know: “Exactly where did the path go wrong?”
This problem asks you to return the specific node where the cycle begins. If no cycle exists, return None.
The Intuition: The Mathematical “Reset”
Detecting the cycle is only Phase 1. Once the Tortoise and the Hare meet, we need a “secret trick” to find the cycle’s entrance.
The math works like this: The distance from the Head of the list to the Cycle Start is exactly equal to the distance from the Meeting Point to the Cycle Start (moving forward through the loop).
Python Code Implementation
We use the two-pointer technique to find the meeting point, then reset one pointer to the start to find the entrance.
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
# Phase 1: Find if a cycle exists and where they meet
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Phase 2: Find the entrance
# Reset one pointer to the head
entry = head
while entry != slow:
entry = entry.next
slow = slow.next
return entry # Both meet at the cycle start
return None
Step-by-Step Dry Run
Let’s use a list where the cycle starts at node (2):
1 → 2 → 3 → 4 → (back to 2)
-
Phase 1: Slow and Fast move. As we saw in LeetCode 141, they eventually meet at node 4.
-
Phase 2: We keep
slowat node 4 and place a new pointerentryat the head (node 1). -
Step 1: Move
entryto node 2; moveslowto node 2 (following the cycle). -
Match! Both pointers are now at node 2. This is the entrance.
Final Result: Node 2.
Key Takeaways for Technical Interviews
-
Time Complexity: O(n). Even though we have two phases, we traverse the list a linear number of times.
-
Space Complexity: O(1). We are not using a Hash Set to store nodes; we are only moving three pointers (
slow,fast, andentry). -
The “Why”: Why does this work? If L_1 is the distance to the entrance and L_2 is the distance from the entrance to the meeting point, the math proves that moving from the head and the meeting point simultaneously at the same speed will lead you to the entrance.
Get the Full Source Code
Want to test this on your local machine? I’ve uploaded the complete Python script, including the ListNode class and a helper function to create cycles for testing.
Frequently Asked Questions (FAQs)
1. Why reset to the head?
Mathematical proof shows that the distance from the head to the cycle start is congruent to the distance from the meeting point to the cycle start. Resetting one pointer allows us to “bridge” that gap.
2. Can I use a Hash Set instead?
Yes, you could store node references in a Set. When you see a node for the second time, that’s your entrance. However, that costs O(n) space, and an interviewer will almost always ask you to optimize it to O(1) using Floyd’s.
3. What happens if there is no cycle?
The while fast and fast.next loop will terminate when it hits None, and the function will correctly return None.
Mastered the cycle? Now that you can find the entrance, you’ve conquered the most difficult part of Linked List traversal. Next, we’ll look at how to Reorder a List to optimize search patterns!
🎯 Build a Real Project (Don’t Stop at Theory!)
If you really want to master Linked Lists, don’t just solve problems — build something real.
👉 I’ve created a complete DSA Project – Expense Tracker using only:
- Singly Linked List
- Basic operations (insert, delete, reverse, traversal)
🔗 [Click here to explore the full project]
This will help you:
- Understand real-world use cases
- Strengthen DSA concepts
- Prepare for interviews + projects
