Linked List: Program to detect a cycle in given linked list

Write a program to detect a cycle or loop in a linked list

Approach

• A cycle is present in Linked List when the last node points to any other node in the linked list
  instead of pointing to null which forms a loop
• If you iterate through such a linked list it will never end and you will iterate in a loop
• To detect a loop we use two pointers slow and fast to traverse the linked list
• For each iteration slow pointer points to its immediate next node while fast pointer points to to its next’s next node
  Hence the name fast and slow
• If fast and slow meet at anytime again after starting point then loop is detected in the linked list

Example

Here, in the example the last node 5 points to node 3, forming a cycle/loop.

Algorithm

1. Create two pointers, say fast and slow and set to points on the head node,also set the flag as 0
2. While slow is not NULL and fast is not NULL and fast.next is not NULL.set
   • slow = slow.next
   • fast = fast.next.next
3. If fast = slow then set flag to 1 and exit from loop
4. After the loop is completed, if the flag is 1 then the loop is present in the linked list
5. Else loop is not present in the linked list

Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

Java Code

import java.util.*;

 class DetectCycleInLL{
        
        class Node {
            // initialising data field and next pointer of node
            int data;
            Node next;
         
            Node(int d) {
                this.data = d;
                this.next = null;
            }
        }
     
        Node head;
     
        // creating a linked list using array
        public void buildLinkedlist(int A[], int noOfNodes) {
            int i;
            Node temp, last;
            temp = new Node(A[0]);
            temp.next = null;
            head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(A[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
     
        //printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
        }
     
        public void detectCycle() {
            int flag=0;
            Node slow, fast;
            slow = fast = head;
            while (slow != null && fast != null && fast.next!=null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    flag = 1;
                    break;
                }
            }
            if(flag==1)
            {
                System.out.println("Cycle detected in given LinkedList");
            }
            else{
                System.out.println("Cycle is not detected in given LinkedList");
            }
     
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 1, 2, 3, 4, 5 };
            int numberOfNodes = 5;
            // initialising object of linkedlist class
            DetectCycleInLL ll = new DetectCycleInLL();
            ll.buildLinkedlist(linkedlistElements, numberOfNodes);
            System.out.print("Given Linked List ");
            ll.printLinkedlist();
    
            // creating a cycle in the linked list
            ll.head.next.next.next.next=ll.head.next.next;
            
            // detecting if the linked list has a cycle present
            ll.detectCycle();
     
        }
  }

Output

Given Linked List 1 -> 2 -> 3 -> 4 -> 5
Cycle detected in given LinkedList