How to find loops or cycles in Linked List in Java

In last few months, I have been gone through interviews in many IT MNC companies. I am sharing all questions to everybody one-by-one. I was asked this question "Write a program to find out circular node in Linked List".

In order to solve linked list related algorithmic in Java, you need to be familiar with the concept of single linked list, doubly linked list and circular linked list. A linked list is a collection of nodes. Each node contains two parts: data and address, where address part points to another node in linked list. Last node of linked list (also called tail node) points to null. If a linked list contains a loop or cycle it is known as circular or cyclic linked list.

Below is the image of a linked list containing a circular node:

Algorithm

We can use two pointer approach to check if a linked list contains a circular node or not.

In two pointer approach, two pointers, one is fast and other is slow is used while iterating over linked list. Fast pointer moves two nodes in each iteration, while slow pointer moves to one node. If linked list contains loop or cycle than both fast and slow pointer will meet at some point during iteration. If they don't meet and fast or slow will point to null, then linked list is not cyclic and it doesn't contain any loop. Below are the steps of algorithm to find out circular node:

• Use two pointers fast and slow
• Move fast two nodes and slow one node in each iteration
• If fast and slow meet then linked list contains cycle
• If fast points to null or fast.next points to null then linked list is not cyclic

Java Program

Below is the java program to find out the circular loop in a linked list:

public class LinkedList {
    private Node head;
    public LinkedList() { 
        this.head = new Node("head"); 
    }   
    public Node head() { 
        return head;
    }
   
    public void add(Node node) {
        Node current = head;
       
        //find last element of LinkedList
        while(current.next() != null){
            current = current.next();
        }
        //appending new node to last node in LinkedList
        current.setNext(node);
    }
   
    boolean hasLoop() {
        Node slow = this.head;
        Node fast = this.head;

        while(fast != null && fast.next != null) {
            slow = slow.next;          // 1 hop
            fast = fast.next.next;     // 2 hops 

            if(slow == fast) 
               return true;
        }
        return false; 
    }

   
    @Override
    public String toString(){
        StringBuilder builder = new StringBuilder();
        Node current = head.next();
        List<String> list = new ArrayList<String>();
        
        while (current != null){
            if(list.contains(current.data)) {
                break;
            }
            list.add(current.data);
            current = current.next();
        }
        for (String str : list) {
            builder.append(str).append("-->");
        }

        return builder.delete(builder.length() - 3, builder.length()).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; 
        }

        @Override
        public String toString() {
            return this.data;
        }
    }
}

public class TestLinkedList {

    public static void main(String args[]) {

        //creating LinkedList with 5 elements including head
        LinkedList list = new LinkedList();
        list.add(new LinkedList.Node("100"));
        LinkedList.Node loop = new LinkedList.Node("200");
        list.add(loop);
        list.add(new LinkedList.Node("300"));
        list.add(new LinkedList.Node("400"));
        list.add(loop);

        System.out.println("Linked List : " + list);
        if(list.hasLoop()){
            System.out.println("Linked List contains cycles or loop");
        }
        else{
            System.out.println("Linked List doesn't not have cycles or loop");
        }    
    } 
   
}

Output:
Linked List : 100-->200-->300-->400
Linked List contains cycles or loop

I tried my best to explain the problem and the approach to solve the problem. Please feel free to post comments, suggestions and feedback to improve the article and make the content of the article valuable.