Check If A Linked List Is Circular Linked List

Problem Statement

We are given a Singly LinkedList. We need to check if it is a Circular LinkedList or not. 

Approach

First, we store the Head of LinkedList. Now we will start to iterate the LinkedList. If we reach the NULL or we reach the Head, we will break from there and check if we reached the head, then the LinkedList is circular else not.

There is a flaw in the above approach.

The above approach will run in an infinite loop for the following LinkedList.

To correctly check if a linked list is a circular linked list, we need to traverse the linked list using two pointers. The first pointer will move one node at a time, while the second pointer will move two nodes at a time. If the linked list is not circular, then the second pointer will reach the end of the list and will be NULL. If the linked list is circular, the second pointer will eventually meet the first pointer.

Algorithm

• Initialise two pointers, slow_ptr and fast_ptr, to the head of the linked list.
   
• Traverse the linked list using the pointers until the fast pointer reaches the end of the list (i.e., NULL), or both pointers meet.
   
• If the fast pointer reaches the end of the list (i.e., NULL), then the linked list is not circular. Return false.
   
• If the fast and slow pointer meets, then the linked list is circular. Return true.

 Dry run

Suppose we have a linked list as below:

• Initialise two pointers, slow_ptr and fast_ptr, to the head.

• Slow pointer move by one and fast pointer move by 2

• Next step

• Next step

• Next step

• Next Step

• In this step, both the pointer meet at 13, which results true.

C++ Implementation

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

bool hasCycle(ListNode *head) {
    // initialize two pointers, slow_ptr and fast_ptr, to the head of the linked list
    ListNode *slow_ptr = head;
    ListNode *fast_ptr = head;
   
    // traverse the linked list until the fast_ptr reaches the end (NULL) or encounters the slow_ptr
    while (fast_ptr != NULL && fast_ptr->next != NULL) {
    	// move the slow_ptr one step at a time
        slow_ptr = slow_ptr->next; 
        
        // move the fast_ptr two steps at a time
        fast_ptr = fast_ptr->next->next; 
       
       
       	// if the two pointers meet, the linked list is circular
        if (slow_ptr == fast_ptr) { 
            return true;
        }
    }
   
   	// if the fast_ptr reaches the end, the linked list is not circular
    return false; 
}

int main() {
    // create a circular linked list with five nodes
    ListNode *head = new ListNode(26);
    ListNode *node2 = new ListNode(34);
    ListNode *node3 = new ListNode(84);
    ListNode *node4 = new ListNode(69);
    ListNode *node5 = new ListNode(71);
   
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    
    // make the linked list circular by connecting the last node to the third node
    node5->next = node3; 
   
    // check if the linked list is circular
    if (hasCycle(head)) {
        std::cout << "The linked list is circular." << std::endl;
    } else {
        std::cout << "The linked list is not circular." << std::endl;
    }
   
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Java Implementation

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public static boolean hasCycle(ListNode head) {
        // initialize two pointers, slow_ptr and fast_ptr, to the head of the linked list
        ListNode slow_ptr = head;
        ListNode fast_ptr = head;
       
        // traverse the linked list until the fast_ptr reaches the end (null) or encounters the slow_ptr
        while (fast_ptr != null && fast_ptr.next != null) {
        
        	// move the slow_ptr one step at a time
            slow_ptr = slow_ptr.next; 
            
            // move the fast_ptr two steps at a time
            fast_ptr = fast_ptr.next.next; 
           
           	// if the two pointers meet, the linked list is circular
            if (slow_ptr == fast_ptr) { 
                return true;
            }
        }
       
        return false; // if the fast_ptr reaches the end, the linked list is not circular
    }
   
    public static void main(String[] args) {
        // create a circular linked list with five nodes
        ListNode head = new ListNode(26);
        ListNode node2 = new ListNode(74);
        ListNode node3 = new ListNode(89);
        ListNode node4 = new ListNode(43);
        ListNode node5 = new ListNode(54);
       
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        
        // make the linked list circular by connecting the last node to the third node
        node5.next = node3; 
       
        // check if the linked list is circular
        if (hasCycle(head)) {
            System.out.println("The linked list is circular.");
        } else {
            System.out.println("The linked list is not circular.");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Complexity

Time Complexity

O(n), where n is the number of nodes in the linked list.

Reason: The above code needs to visit every node in the linked list at most twice, once by the slow_ptr and once by the fast_ptr. The time complexity is dominated by the traversal of the linked list, which takes O(n) time in the worst case.

Space Complexity

O(1)

Reason: The above code uses only two pointers, slow_ptr and fast_ptr, to traverse the linked list, and no extra data structures are created.

Frequently Asked Questions

Can we access the random element of the LinkedList?

We can not access any element of the LinkedList directly. We don’t have direct access to every element of LinkedList. If we want to access the ith element of the LinkedList, then we need to traverse the LinkedList till the ith index.

What is the purpose of a circular linked list?

A circular linked list can be used to represent data that forms a loop or cycle. For example, a circular linked list can be used to represent a round-robin scheduling algorithm, where a set of tasks are executed in a fixed order.

How do you create a circular linked list?

To create a circular linked list, you need to make the last node point back to the first node, forming a cycle. You can do this by setting the next pointer of the last node to the first node.

How do you break a circular linked list?

To break a circular linked list, you need to point the last node to NULL instead of the first node. You can do this by setting the previous node's next pointer to NULL.

What was the flaw in the first approach?

There will be a few cases in which the LinkedList will have a cycle with the Starting point being a node other than Head. In such cases, you will start your while loop from the second node. Now you will never encounter neither NULL nor the Head. 

Conclusion

We have learned about circular linked lists and how to check if a linked list is circular. We have discussed the algorithm for checking if a linked list is circular, which involves using two pointers, slow_ptr and fast_ptr, that traverse the linked list. 

If you want to learn more topics related to these, follow below links:

• Bucket Sort.
   
• Cherry Pickup
   

If you want to learn more about Linked List and want to practice some questions which require you to take your basic knowledge on  Linked List a notch higher, then you can visit our Guided Path for  Linked List. 

Until then, All the best for your future endeavours, and Keep Coding.