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



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list