Detect Cycle in Linked List | Java Fresher Interview

Direct Answer

Floyd's tortoise-and-hare: move slow one node and fast two nodes each step. If they ever meet, the list has a cycle; if fast reaches null, it doesn't. O(n) time, O(1) space. To find the cycle's start, reset one pointer to the head after they meet and advance both one step at a time until they meet again.

Deep Dive & Architecture

Floyd's cycle detection uses two references from the head. slow moves one node per step and fast moves two. If fast reaches null, the list ends and has no cycle. If the references become equal, a cycle exists.

Worked example: 1 -> 2 -> 3 -> 4, with 4.next = 2

After one round, slow is at 2 and fast at 3. After two, slow is at 3 and fast is back at 2. After three, both are at 4. Neither pointer needed a visited set.

The reason a meeting is guaranteed is relative speed. Once both pointers enter a cycle of length c, fast gains one node on slow during every round. Their gap modulo c therefore changes by one until it becomes zero.

Check fast != null && fast.next != null before the two-node move. This avoids a null access on an acyclic list. Comparing node references is also essential; equal values do not mean the same node.

The method is O(n) time and O(1) extra space. To find the cycle entry, move one pointer back to the head after the meeting, then advance both one step at a time; their next meeting is the entry node.

Code Example

Node detectCycleStart(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {                 // cycle confirmed
            slow = head;                    // reset one pointer
            while (slow != fast) { slow = slow.next; fast = fast.next; }
            return slow;                    // entry point of the loop
        }
    }
    return null;                            // no cycle
}

// 1->2->3->4->5->3(back): meet inside loop, reset, both walk -> meet at 3

Common Mistakes & Pitfalls

• HashSet of visited: O(n) space when Floyd's gives O(1).
• NPE: guard fast != null && fast.next != null.
• Comparing values: compare node references.
• Skipping the reset proof: know the meeting->head reset finds the cycle start.