How to find if Linked List contains cycle in Java

In this tutorial, we will see how to check if the given linked list contains a cycle or loop in java. A linked list is a data structure, it has a collection of nodes. Each node has two parts data and address, where address part points to another node in linked list. The last node of linked list, referred as tail, points to null. We can use two pointer approach to solve our program.

We will use two pointers, fast and slow while iterating over linked list. The fast pointer moves two nodes in each iteration, while slow pointer moves one node in each iteration.

If linked list contains loop or cycle then both fast and slow pointer will meet at some point during iteration. If they don’t meet and fast or slow points to null, then linked list is not cyclic and it doesn’t contain any loop. This algorithm is called Floyd’s cycle finding algorithm.



Java Code to find if Linked List contains a cycle

This Java program uses LinkedList and Node class. Also, isCyclic() method of linked list is used to implement logic to find if linked list contains cycle or not.  isCyclic() returns true if linked list is cyclic otherwise it returns false.

public class LinkedList { 
    private Node head; 
    public LinkedList() {
        this.head = new Node("head"); 
        
    } 
    public Node head() { 
        return head;
        
    } 
    public void appendIntoTail(Node node) { 
        Node current = head; 

        while(current.next() != null){ 
            current = current.next(); 
            
        } 

        current.setNext(node); 
        
    } 

        public boolean isCyclic(){ 
            Node fast = head; 
            Node slow = head; 
            while(fast!= null && fast.next != null){ 
                fast = fast.next.next; 
                slow = slow.next; 
                if(fast == slow ){ return true; 
                    
                } } 
                return false; 
            
        } 

        public String toString(){ 
            StringBuilder sb = new StringBuilder(); 
            Node current = head.next(); 
            while(current != null){ 
                sb.append(current).append("-->"); 
                current = current.next(); 
                
            } 
            sb.delete(sb.length() - 3, sb.length()); 
            return sb.toString(); 
            
        } 
        public static class Node { 
            private Node next; 
            private String data; 
            public Node(String data) {
                this.data = data; 
                
            } 
            public String data() { 
                return data; 
                
            } 
            public void setData(String data) { 
                this.data = data;
                
            } 
            public Node next() { 
                return next; 
                
            } 
            public void setNext(Node next) { 
                this.next = next;
                } 

                public String toString() { 
                    return this.data; 
                    
                } } 
public static void main(String args[]) { 
    LinkedList linkedList = new LinkedList(); 
    linkedList.appendIntoTail(new LinkedList.Node("101")); 
    linkedList.appendIntoTail(new LinkedList.Node("201")); 
    linkedList.appendIntoTail(new LinkedList.Node("301")); 
    linkedList.appendIntoTail(new LinkedList.Node("401")); 
    System.out.println("Linked List : " + linkedList); 
    if(linkedList.isCyclic()){ 
        System.out.println("Linked List is cyclic "); 
        
    }
    else{ 
        System.out.println("LinkedList is not cyclic "); 
        
    } }
}

 

Output:

Linked List : 101-->201-->301-->401
LinkedList is not cyclic

Hope the above code helps you to find if there is a cycle in a Linked List in Java.

Also read,

Generate random matrix in Java

Leave a Reply

Your email address will not be published. Required fields are marked *