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();
 }
}