Detect the Start of a Cycle

Finding not just whether a linked list has a cycle but exactly where that cycle begins is a real-world need whenever you’re dealing with repeating events or loops—like detecting ring buffers gone awry or identifying the entry point of a routing loop. It showcases deep pointer reasoning and neat math trickery.

Problem Statement

Given the head of a singly linked list, return the node where the cycle begins, or null if there is no cycle. You must not modify the list and aim for O(n) time and O(1) extra space.

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

// Function signature:
public ListNode detectCycle(ListNode head);

1. Clarify Requirements Before Jumping Into Code

I’ll ask a few clarifications:

• Is it safe to assume either exactly one cycle or none? Yes.

• Should I return the actual node object where the cycle starts? Yes.

• Can I use extra data structures? O(1) extra space is expected.

• Is the list length bound known? It could be large, so no recursion that blows the stack.

2. Identify the Category of the Question

This falls squarely in linked-list cycle detection and pointer manipulation. Common linked-list patterns include:

• Fast and slow pointer for cycle detection

• Finding list midpoint

• Reversing a list

• Merge two lists

• Removing Nth node from end

Detecting the cycle start builds on fast/slow pointer plus extra math to locate the entry.

3. Consider a Brute-Force Approach to Understand the Problem

A brute-force way is to walk each node and keep visited nodes in a hash set. The first time you see a node twice, that’s the cycle start.

• Time: O(n)

• Space: O(n) for the set

• Drawback: uses linear extra memory

4. Brainstorm More Solutions

I want O(1) extra space. I know Floyd’s Tortoise and Hare can detect a cycle by meeting inside the loop. But how do I find the entry?

First I detect the cycle: move the slow pointer by one and the fast pointer by two until they meet (or fast hits null). Once they meet, I know a cycle exists.

To find the start, recall this trick: if I reset the slower pointer to the head node, then advance both pointers one step at a time, they will meet at the cycle’s entry.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Hash Set	O(n)	O(n)	Simple to write	Uses extra memory
Floyd + Reset	O(n)	O(1)	No extra memory, optimal	Requires understanding math
Marking Nodes	O(n)	O(1)	Could overwrite pointers to mark	Destroys list structure

Floyd’s two-pointer with reset is ideal for O(1) space without list mutation.

6. Write Pseudocode to Structure Your Thoughts

function detectCycle(head):
  if head is null: return null

  // Phase 1: Detect cycle
  slow = head
  fast = head
  while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
      // Phase 2: Find entry
      ptr1 = head
      ptr2 = slow
      while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next
      return ptr1

  return null  // no cycle

7. Consider Edge Cases

• Empty list → returns null

• Single node, no cycle → returns null

• Single node, self-cycle → returns that node

• Cycle at head → detection and reset still finds head

• Cycle late in list → reset correctly walks to entry

8. Write Full Code Syntax

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

        ListNode slow = head;
        ListNode fast = head;

        // Phase 1: find meeting point
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // Phase 2: locate entry
                ListNode ptr1 = head;
                ListNode ptr2 = slow;
                while (ptr1 != ptr2) {
                    ptr1 = ptr1.next;
                    ptr2 = ptr2.next;
                }
                return ptr1;
            }
        }

        return null; // no cycle
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Helper methods buildList and linkCycle omitted for brevity

    // Test 1: empty list
    assert sol.detectCycle(null) == null;

    // Test 2: single node, no cycle
    ListNode a = new ListNode(1);
    assert sol.detectCycle(a) == null;

    // Test 3: single node, self-cycle
    a.next = a;
    assert sol.detectCycle(a) == a;

    // Test 4: two nodes, cycle at second
    ListNode b = new ListNode(2);
    a.next = b;
    b.next = a;
    assert sol.detectCycle(a) == a;

    // Test 5: longer list with cycle start at node 3
    ListNode head = new ListNode(0), curr = head;
    for (int i = 1; i <= 5; i++) {
        curr.next = new ListNode(i);
        curr = curr.next;
    }
    // link tail back to node 2 (value=2)
    ListNode cycleStart = head.next.next;
    curr.next = cycleStart;
    assert sol.detectCycle(head) == cycleStart;

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Two-phase Floyd’s algorithm finds both cycle presence and entry without extra memory.

• Always handle base cases (null, single node) before complex logic.

• Writing clear pseudocode for detection then entry-finding clarifies pointer moves.

• Discussing trade-offs between hash-based and pointer-based approaches shows depth of understanding.

• Visual metaphors—runner laps walker on a track—make two-pointer reasoning intuitive.

Good Luck and Happy Coding!