package DataStructures.Lists;

import java.util.Scanner;

public class CreateAndDetectLoop {

	/**
	 * Prints the linked list.
	 * 
	 * @param	head	head node of the linked list
	 */
	static void printList(Node head) {		
        Node cur = head;
        
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
    }

	/**
	 * Creates a loop in the linked list.
	 * @see 	<a href="https://www.geeksforgeeks.org/make-loop-k-th-position-linked-list/">
	 * 			GeeksForGeeks: Make a loop at K-th position</a>
	 * @param	head	head node of the linked list
	 * @param	k		position of node where loop is to be created
	 */
    static void createLoop(Node head, int k) {
    	if (head == null)
    		return;
        Node temp = head;
        int count = 1;
        while (count < k) { 		// Traverse the list till the kth node
            temp = temp.next;
            count++;
        }

        Node connectedPoint = temp;

        while (temp.next != null) 	// Traverse remaining nodes
            temp = temp.next;

        temp.next = connectedPoint; // Connect last node to k-th element
    }

    /**
	 * Detects the presence of a loop in the linked list.
	 * @see 	<a href="https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare">
	 * 			Floyd's Cycle Detection Algorithm</a>
	 * 
	 * @param 	head 	the head node of the linked list
	 * 
	 * @return 		 	true if loop exists else false
	 */
    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 (fptr == sptr)
    			return true;
    	}
    	
    	return false;
    }

    public static void main(String[] args) {
        SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter the number of elements to be inserted: ");
        int n = sc.nextInt();
        System.out.printf("Enter the %d elements: \n", n);
        while (n-- > 0)
        	singlyLinkedList.insert(sc.nextInt());
        
        System.out.print("Given list: ");
        printList(singlyLinkedList.getHead());
        System.out.println();
        
        System.out.println("Enter the location to generate loop: ");
        int k = sc.nextInt();
        
        createLoop(singlyLinkedList.getHead(), k);
        
        if (detectLoop(singlyLinkedList.getHead()))
            System.out.println("Loop found");
        else
            System.out.println("No loop found");
        
        sc.close();
    }
}