Cycle Detection

Problem Statement

Write a Java program that extends a singly linked list implementation to detect if the list contains a cycle using Floyd’s Tortoise and Hare algorithm. The linked list consists of nodes, each containing an integer value and a reference to the next node. A cycle exists if a node’s next pointer points to an earlier node in the list. The program should return true if a cycle is detected and false otherwise, and test the implementation with both cyclic and acyclic lists of varying sizes, including empty lists, single-node lists, and multi-node lists with or without cycles. You can visualize this as checking if a chain of numbered cards loops back to an earlier card, using two pointers moving at different speeds to detect the loop.

Input:

• A singly linked list of integers (e.g., 1→2→3→4→2, where 4 points back to 2, forming a cycle). Output: A boolean indicating whether the list contains a cycle (true for cyclic, false for acyclic), along with a string representation of the list for clarity. Constraints:
• The list size is between 0 and 10^5.
• Node values are integers in the range [-10^9, 10^9].
• The list may be empty or contain a cycle at any position. Example:
• Input: 1→2→3→4→2 (cycle: 4→2)
• Output: true
• Explanation: A cycle exists as 4 points back to 2.
• Input: 1→2→3→null
• Output: false
• Explanation: No cycle, as the list terminates at null.
• Input: []
• Output: false
• Explanation: An empty list has no cycle.

Pseudocode

CLASS Node
    SET value to integer
    SET next to Node (null by default)
ENDCLASS

FUNCTION hasCycle(head)
    IF head is null OR head.next is null THEN
        RETURN false
    ENDIF
    SET slow to head
    SET fast to head
    WHILE fast is not null AND fast.next is not null
        SET slow to slow.next
        SET fast to fast.next.next
        IF slow equals fast THEN
            RETURN true
        ENDIF
    ENDWHILE
    RETURN false
ENDFUNCTION

FUNCTION toString(head, limit)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    SET count to 0
    CREATE visited as new set
    WHILE current is not null AND count < limit
        IF visited contains current THEN
            APPEND "->" + current.value + " (cycle)" to result
            BREAK
        ENDIF
        ADD current to visited
        APPEND current.value to result
        IF current.next is not null THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
        INCREMENT count
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of linked lists (some cyclic, some acyclic)
    FOR each testCase in testCases
        PRINT test case details
        CALL hasCycle(testCase.head)
        PRINT whether cycle exists
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a Node class with: a. An integer value. b. A next pointer to the next node.
2. In hasCycle (Floyd’s Tortoise and Hare): a. If head or head.next is null, return false (no cycle possible). b. Initialize slow and fast pointers to head. c. While fast and fast.next are not null:
   • Move slow one step, fast two steps.
   • If slow equals fast, a cycle exists (return true). d. If fast reaches null, no cycle exists (return false).
3. In toString: a. If head is null, return "[]". b. Traverse the list with a limit to avoid infinite loops in cyclic lists. c. Use a set to detect cycles and indicate them in the output. d. Return space-separated values with cycle annotation if present.
4. In main, test with empty, single-node, multi-node acyclic, and cyclic lists.

Java Implementation

import java.util.*;

public class CycleDetection {
    // Node class for the linked list
    static class Node {
        int value;
        Node next;

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

    // Detects if the linked list has a cycle using Floyd’s algorithm
    public boolean hasCycle(Node head) {
        if (head == null || head.next == null) {
            return false;
        }
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    // Converts linked list to string for output, handling cycles
    public String toString(Node head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        Node current = head;
        int count = 0;
        int limit = 100; // Prevent infinite loop
        Set<Node> visited = new HashSet<>();
        while (current != null && count < limit) {
            if (visited.contains(current)) {
                result.append("->").append(current.value).append(" (cycle)");
                break;
            }
            visited.add(current);
            result.append(current.value);
            if (current.next != null) {
                result.append(" ");
            }
            current = current.next;
            count++;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Node head;
        boolean hasCycle;

        // Creates acyclic list from values
        TestCase(int[] values) {
            this.hasCycle = false;
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new Node(values[0]);
            Node current = head;
            for (int i = 1; i < values.length; i++) {
                current.next = new Node(values[i]);
                current = current.next;
            }
        }

        // Creates cyclic list with cycle at specified position
        TestCase(int[] values, int cyclePos) {
            this.hasCycle = true;
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new Node(values[0]);
            Node current = head;
            Node cycleNode = null;
            for (int i = 1; i < values.length; i++) {
                current.next = new Node(values[i]);
                current = current.next;
                if (i == cyclePos) {
                    cycleNode = current;
                }
            }
            if (cyclePos >= 0 && cyclePos < values.length) {
                current.next = cycleNode; // Create cycle
            }
        }
    }

    // Main method to test cycle detection
    public static void main(String[] args) {
        CycleDetection detector = new CycleDetection();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 2, 3, 4}, 2), // Cyclic: 1→2→3→4→3
            new TestCase(new int[]{1, 2, 3}),       // Acyclic: 1→2→3
            new TestCase(new int[]{}),              // Empty
            new TestCase(new int[]{5}),             // Single node
            new TestCase(new int[]{1, 2, 3, 4, 5}, 0) // Cyclic: 1→2→3→4→5→1
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input list: " + detector.toString(test.head));
            boolean result = detector.hasCycle(test.head);
            System.out.println("Has cycle: " + result + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input list: 1 2 3 4->3 (cycle)
Has cycle: true

Test case 2:
Input list: 1 2 3
Has cycle: false

Test case 3:
Input list: []
Has cycle: false

Test case 4:
Input list: 5
Has cycle: false

Test case 5:
Input list: 1 2 3 4 5->1 (cycle)
Has cycle: true

Explanation:

• Test case 1: List 1→2→3→4 with 4→3 forms a cycle, returns true.
• Test case 2: Acyclic list 1→2→3, returns false.
• Test case 3: Empty list, returns false.
• Test case 4: Single node 5, returns false.
• Test case 5: List 1→2→3→4→5 with 5→1 forms a cycle, returns true.

How It Works

• Node: Stores an integer value and a next pointer.
• hasCycle (Floyd’s Tortoise and Hare):
  • Returns false if list is empty or has one node.
  • Uses slow (moves one step) and fast (moves two steps) pointers.
  • If slow meets fast, a cycle exists.
  • If fast reaches null, no cycle exists.
• toString:
  • Handles cycles by tracking visited nodes and limiting traversal.
  • Outputs values with spaces, appending cycle annotation if detected.
• Example Trace (Test case 1):
  • Input: 1→2→3→4→3 (cycle at 3).
  • slow=1, fast=1.
  • Step 1: slow=2, fast=3.
  • Step 2: slow=3, fast=4.
  • Step 3: slow=4, fast=3.
  • Step 4: slow=3, fast=3 (meet, cycle detected).
  • Return: true.
• Main Method: Tests cyclic (cycle at different positions), acyclic, empty, and single-node lists.

Complexity Analysis Table

Note:

• n is the number of nodes in the list.
• Time complexity: O(n) for hasCycle (Floyd’s algorithm traverses list); O(n) for toString (traverse with cycle detection).
• Space complexity: O(1) for hasCycle (two pointers); O(n) for toString (visited set and StringBuilder).
• Worst case: O(n) time, O(n) space for large lists in output.

✅ Tip: Use Floyd’s Tortoise and Hare algorithm for efficient cycle detection with O(1) space. Test with cycles at different positions to ensure robustness.

⚠ Warning: Ensure pointers are checked for null to avoid null pointer exceptions. Be cautious when printing cyclic lists to avoid infinite loops.