package com.thealgorithms.datastructures.lists;

/**
 * CreateAndDetectLoop provides utility methods for creating and detecting loops
 * (cycles) in a singly linked list. Loops in a linked list are created by
 * connecting the "next" pointer of one node to a previous node in the list,
 * forming a cycle.
 */
public final class CreateAndDetectLoop {

    /**
     * Private constructor to prevent instantiation of this utility class.
     */
    private CreateAndDetectLoop() {
        throw new UnsupportedOperationException("Utility class");
    }

    /**
     * Node represents an individual element in the linked list, containing
     * data and a reference to the next node.
     */
    static final class Node {
        int data;
        Node next;

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

    /**
     * Creates a loop in a linked list by connecting the next pointer of a node
     * at a specified starting position (position2) to another node at a specified
     * destination position (position1). If either position is invalid, no loop
     * will be created.
     *
     * @param head the head node of the linked list
     * @param position1 the position in the list where the loop should end
     * @param position2 the position in the list where the loop should start
     */
    static void createLoop(Node head, int position1, int position2) {
        if (position1 == 0 || position2 == 0) {
            return;
        }

        Node node1 = head;
        Node node2 = head;

        int count1 = 1;
        int count2 = 1;
        // Traverse to the node at position1
        while (count1 < position1 && node1 != null) {
            node1 = node1.next;
            count1++;
        }

        // Traverse to the node at position2
        while (count2 < position2 && node2 != null) {
            node2 = node2.next;
            count2++;
        }

        // If both nodes are valid, create the loop
        if (node1 != null && node2 != null) {
            node2.next = node1;
        }
    }

    /**
     * Detects the presence of a loop in the linked list using Floyd's cycle-finding
     * algorithm, also known as the "tortoise and hare" method.
     *
     * @param head the head node of the linked list
     * @return true if a loop is detected, false otherwise
     * @see <a href="https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare">
     *     Floyd's Cycle Detection Algorithm</a>
     */
    static boolean detectLoop(Node head) {
        Node sptr = head;
        Node fptr = head;

        while (fptr != null && fptr.next != null) {
            sptr = sptr.next;
            fptr = fptr.next.next;
            if (sptr == fptr) {
                return true;
            }
        }
        return false;
    }
}