VSDevelopers, Algorithms Coliseum

Find a loop in Linked List


/*Copyrights to vsdevelopers.io*/
/*For more programs visit vsdevelopers.io */
/*Java program to detect loop in a linked list*/
import java.util.*;;

public class VSDLinkedListLoop {
	// Clss to hold the structure of a node
	private static class VSDNode {
		int data;// data of node
		VSDNode next;// pointer to next elemnt in the list

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

	static VSDNode head = null;

	// Function to insert elements into the linked list
	public static void VSDinsert(int element) {
		VSDNode temp = new VSDNode(element);// making use of temporary node to insert
		if (head == null)
			head = temp;// Inserting first element as head
		else {
			VSDNode x = head;// Temporary node to iterate over list and find last node
			while (x.next != null) {
				x = x.next;
			}
			x.next = temp;// Inserting node at end of Linked list
		}
	}

	// Function to check whether the loop exists or not in a linked list
	public static boolean VSDfindLoop() {
		VSDNode cur = null;// Temporary node
		if (head == null)
			System.out.println("The linked is empty");
		else {
			HashSet<VSDNode> h = new HashSet<VSDNode>();// Hash set to keep trck of elements in the list
			cur = head;
			// Itrating through the list
			while (cur.next != null) {
				// adding elements to the hash set
				h.add(cur);
				// checking whether the element is repeated
				if (h.contains(cur.next)) {
					return true;
				} else
					cur = cur.next;
			}
		}
		return false;

	}

	public static void main(String args[]) {
		VSDinsert(10);
		VSDinsert(11);
		VSDinsert(12);
		VSDinsert(13);
		VSDinsert(14);
		VSDinsert(15);
		VSDinsert(16);
		head.next.next = head;
		boolean b = VSDfindLoop();

		if (b)
			System.out.println("The linked list contains a loop");
		else
			System.out.println("The linked list does not contain a loop");
	}
}

loader