## JAVA EXAMPLE PROGRAMS

Checkout for Promo Codes

# Program: Identify loop/cycle in a LinkedList.

 Problem Description: Write a simple code to identify loop or cycle in a linked list. In general, the last node is null in a Linked list. A loop/cycle exists in a LinkedList when no null is reached as we traverse throughout the LinkedList. There are various ways to identify loop/cycle in a linked list. The below diagram illustrates linked list loop/cycle: Approach 1: Using Hashing Traverse the linked list nodes and keep adding the node addresses in a Hash Table. At any point, if NULL is reached then the loop/cycle doesnot exist, return false. If next of current node points to any of the previously stored nodes in Hash Table, then return true. The disadvantage with above approach is it requires extra storage to keep track of hashes. Approach 2: Floyd’s Cycle-Finding Algorithm Traverse linked list nodes using two pointers. Move first pointer by one step and second pointer by two step. If the pointers meet at the same node then there is a loop. At any point, if NULL is reached then the loop/cycle doesnot exist, return false.

 IdentifyLinkedListLoop package com.java2novice.algos; import java.util.HashSet; import java.util.Set; public class IdentifyLinkedListLoop { static class Node { int data; Node next; Node(int tmp) {data = tmp;} } public static void main(String[] a){ Node n1 = new Node(34); Node n2 = new Node(25); Node n3 = new Node(31); Node n4 = new Node(56); Node n5 = new Node(45); n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5; n5.next = n3; System.out.println("Is loop detected: "+identifyLoopV2(n1)); } static boolean identifyLoopV1(Node head) { /** * In this method, we will keep track of traversed node hash and check with each traversing node. * If any match found, then we noticed Loop. * If we get hash as null, then we didnt find loop. */ Set hash = new HashSet<>(); while (head != null){ if(hash.contains(head)) { return Boolean.TRUE; } hash.add(head); head = head.next; } return Boolean.FALSE; } static boolean identifyLoopV2(Node head) { /** * In this method, we will keep track of two pointers. * One pointer moves one step at a time and second one two steps. * If both pointers are same at any iteration, then the loop exists. */ Node slowMv = head; Node fastMv = head; while (slowMv != null && fastMv != null && fastMv.next != null) { slowMv = slowMv.next; fastMv = fastMv.next.next; if(slowMv == fastMv) { return Boolean.TRUE; } } return Boolean.FALSE; } }

 Output: Is loop detected: true

#### List Of All Interview Programs:

Java2Novice - YouTube Channel
Knowledge Centre
Interface and its usage
Interface is similar to a class which may contain method's signature only but not bodies and it is a formal set of method and constant declarations that must be defined by the class that implements it. Interfaces are useful for declaring methods that one or more classes are expected to implement, capturing similarities between unrelated classes without forcing a class relationship and determining an object's programming interface without revealing the actual body of the class.
Famous Quotations
I don’t know the key to success, but the key to failure is trying to please everybody.
-- Bill Cosby

### Other Interesting Sites

 Reference: Java™ Platform Standard Ed. 7 - API Specification | Java™ Platform Standard Ed. 8 - API Specification | Java is registered trademark of Oracle. Privacy Policy | Copyright © 2022 by Nataraja Gootooru. All Rights Reserved.