Detect a Loop in a Linked List: Floyd's Algorithm Explained

package io.thecodeforge.list;

import java.util.HashSet;
import java.util.Set;

/**
 * Naive cycle detection using a HashSet.
 * Simple but O(n) space — use Floyd's for O(1) space.
 */
public class NaiveLoopDetection {

    // A single node in our linked list
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    /**
     * Naive approach: store every visited node reference in a HashSet.
     * If we encounter a node we've already stored, a cycle exists.
     * Time:  O(n)  — we visit each node at most once
     * Space: O(n)  — we store up to n node references
     */
    public static boolean hasCycleNaive(Node head) {
        Set<Node> visitedNodes = new HashSet<>();

        Node current = head;
        while (current != null) {
            // If this node's reference is already in the set, we've looped back
            if (visitedNodes.contains(current)) {
                return true; // cycle detected
            }
            visitedNodes.add(current); // mark this node as visited
            current = current.next;    // move to the next node
        }
        return false; // reached null — no cycle
    }

    public static void main(String[] args) {
        // Build a list: 1 -> 2 -> 3 -> 4 -> 5 -> null  (no cycle)
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        System.out.println("List with no cycle: " + hasCycleNaive(head)); // false

        // Now create a cycle: node 5's next points back to node 3
        // List becomes: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 3)
        head.next.next.next.next.next = head.next.next; // node5.next = node3

        System.out.println("List with cycle:    " + hasCycleNaive(head)); // true
    }
}

package io.thecodeforge.list;

/**
 * Floyd's Cycle Detection with cycle start identification.
 * Production-grade implementation with null guards and phase separation.
 */
public class FloydCycleDetection {

    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    /**
     * Floyd's Cycle Detection (Tortoise and Hare).
     * Time:  O(n)  — tortoise visits each node at most once before meeting
     * Space: O(1)  — only two pointers, no extra data structures
     *
     * @return the meeting node inside the cycle, or null if no cycle exists
     */
    public static Node detectCycle(Node head) {
        if (head == null || head.next == null) {
            return null; // empty or single-node list can't have a cycle
        }

        Node tortoise = head; // moves 1 step per iteration
        Node hare      = head; // moves 2 steps per iteration

        while (hare != null && hare.next != null) {
            tortoise = tortoise.next;       // 1 step
            hare     = hare.next.next;      // 2 steps

            // If they meet, a cycle exists — return the meeting point
            if (tortoise == hare) {
                return tortoise;
            }
        }

        // hare hit null — no cycle
        return null;
    }

    /**
     * Find the node where the cycle STARTS (not just whether one exists).
     *
     * Mathematical proof sketch:
     *   Let F = distance from head to cycle start
     *       C = length of the cycle
     *       h = distance from cycle start to meeting point (inside cycle)
     *
     *   When they meet:  tortoise travelled F + h
     *                    hare travelled    F + h + n*C  (lapped the cycle n times)
     *   Since hare travels 2x as far:  2(F + h) = F + h + n*C
     *   Simplifying:                   F = n*C - h
     *   This means: a pointer starting at head AND a pointer starting at the
     *   meeting point, both moving one step at a time, will meet exactly at
     *   the cycle start node.
     */
    public static Node findCycleStart(Node head) {
        Node meetingPoint = detectCycle(head);
        if (meetingPoint == null) {
            return null; // no cycle
        }

        Node pointerFromHead    = head;         // starts at the beginning
        Node pointerFromMeeting = meetingPoint; // starts at the meeting point

        // Both move one step at a time — they converge at the cycle start
        while (pointerFromHead != pointerFromMeeting) {
            pointerFromHead    = pointerFromHead.next;
            pointerFromMeeting = pointerFromMeeting.next;
        }

        return pointerFromHead; // this is the cycle start node
    }

    public static void main(String[] args) {
        // Build list: 10 -> 20 -> 30 -> 40 -> 50
        //                          ^              |
        //                          |______________|  (cycle starts at node 30)
        Node head    = new Node(10);
        Node node20  = new Node(20);
        Node node30  = new Node(30); // <-- cycle start
        Node node40  = new Node(40);
        Node node50  = new Node(50);

        head.next   = node20;
        node20.next = node30;
        node30.next = node40;
        node40.next = node50;
        node50.next = node30; // cycle: 50 points back to 30

        // --- Detect cycle ---
        Node meeting = detectCycle(head);
        if (meeting != null) {
            System.out.println("Cycle detected! Meeting point value: " + meeting.value);
        } else {
            System.out.println("No cycle found.");
        }

        // --- Find cycle start ---
        Node cycleStart = findCycleStart(head);
        if (cycleStart != null) {
            System.out.println("Cycle starts at node with value: " + cycleStart.value);
        }

        // --- Verify on a clean list ---
        Node cleanHead = new Node(1);
        cleanHead.next = new Node(2);
        cleanHead.next.next = new Node(3);
        System.out.println("Clean list cycle detected: " + (detectCycle(cleanHead) != null));
    }
}

package io.thecodeforge.list;

/**
 * Extends Floyd's detection with cycle length measurement.
 * Compositional design: detect -> find start -> measure length.
 */
public class CycleLengthFinder {

    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // --- Reuse Floyd's detection from earlier ---
    public static Node detectCycle(Node head) {
        if (head == null || head.next == null) return null;

        Node tortoise = head;
        Node hare     = head;

        while (hare != null && hare.next != null) {
            tortoise = tortoise.next;
            hare     = hare.next.next;
            if (tortoise == hare) return tortoise;
        }
        return null;
    }

    public static Node findCycleStart(Node head) {
        Node meetingPoint = detectCycle(head);
        if (meetingPoint == null) return null;

        Node fromHead    = head;
        Node fromMeeting = meetingPoint;

        while (fromHead != fromMeeting) {
            fromHead    = fromHead.next;
            fromMeeting = fromMeeting.next;
        }
        return fromHead;
    }

    /**
     * Measures the number of nodes in the cycle.
     * Strategy: start at the cycle's first node, walk until we return to it.
     * The step count equals the cycle length.
     */
    public static int measureCycleLength(Node head) {
        Node cycleStart = findCycleStart(head);
        if (cycleStart == null) {
            return 0; // no cycle
        }

        int cycleLength = 1;              // we count the start node itself
        Node walker = cycleStart.next;    // begin one step ahead

        // Walk until we lap back to cycleStart
        while (walker != cycleStart) {
            walker = walker.next;
            cycleLength++;
        }

        return cycleLength;
    }

    public static void main(String[] args) {
        // Build: 5 -> 10 -> 15 -> 20 -> 25 -> 30
        //                    ^                  |
        //                    |__________________| (cycle of length 4: 15->20->25->30->15)
        Node head   = new Node(5);
        Node node10 = new Node(10);
        Node node15 = new Node(15); // cycle start
        Node node20 = new Node(20);
        Node node25 = new Node(25);
        Node node30 = new Node(30);

        head.next   = node10;
        node10.next = node15;
        node15.next = node20;
        node20.next = node25;
        node25.next = node30;
        node30.next = node15; // close the cycle at node15

        System.out.println("Cycle detected : " + (detectCycle(head) != null));
        System.out.println("Cycle starts at: " + findCycleStart(head).value);
        System.out.println("Cycle length   : " + measureCycleLength(head) + " nodes");

        // Bonus: no-cycle case
        Node cleanList = new Node(1);
        cleanList.next = new Node(2);
        cleanList.next.next = new Node(3);
        System.out.println("Clean list cycle length: " + measureCycleLength(cleanList));
    }
}