How to check if a linked list is a circular linked list

A circular linked list is a type of linked list in which the head and tail of the list are joined together to form a looped structure. It proves to be very useful in solving various problems.

Understanding the problem

Let's suppose we have a linked list and have to determine if it is a circular link list or not. In short, we need to check whether a loop exists in the structure.

Solution

One way of solving this problem is to traverse the list using a temporary pointer starting from the head. If the temporary pointer becomes equal to the head pointer, the list is circular. If the temporary pointer becomes null, the list is not circular.

Code

Let's use the following C++ program to check whether a linked list is circular or not:

#include<iostream>
using namespace std;
struct node{
	int data;
	struct node* next;
};
node * insertnode(int x){
	struct node *temp = new node;
	temp->data = x;
	temp->next = nullptr;
	return temp;
}
// The function to check if the data structure is a circular link list 
bool iscircular(struct node *head){
	if (head == nullptr)
	return true;
	struct node *temp = head->next;
	while (temp != nullptr && temp != head){
	temp = temp->next;
	}
	return (temp == head);
}
void print(node* head){
	node* temp = head;
	if (head != nullptr) {
		do {
			cout << temp->data << " ";
			temp = temp->next;
		} while (temp != head && temp != nullptr);
	}
	if(temp!=nullptr){
		cout<< "->(looped)";
	}
}
int main(){
  //example 1:
	struct node* head = insertnode(1);
	head->next = insertnode(2);
	head->next->next = insertnode(3);
	head->next->next->next = insertnode(4);
	print(head);
	bool yes = iscircular(head);
  	if(yes == true){
    	cout<<endl<<"The linked list is circular"<<endl;
  	}
  	else{
        cout<<endl<<"The linked list is not circular"<<endl;
  	}	
	
  	yes = false;
  	//example 2 (looping the above list):
	head->next->next->next->next = head;
	print(head);
  	yes = iscircular(head);
  	if(yes == true){
    	cout<<endl<<"The linked list is circular"<<endl;
  	}
	else{
        cout<<endl<<"The linked list is not circular"<<endl;
  	}
	return 0;
}

Explanation

Lines 4–7: A node struct form the building block of our list. It contains a data integer and a next node pointer.

Lines 9–14: This is the insertnode function that adds new nodes to the linked list in a looped manner.

Lines 16–27: This is the iscircular function where we traverse each node starting from the node. If the temp pointer reaches back to the head , the linked list is circular. If the temp pointer becomes null, the linked list is not circular.

Lines 31–42: A print function is defined by traversing the list.

Lines 45–75: The main function calls the insertnode function to add nodes. It also calls the iscircular function defined above.

Time complexity

The above code's time complexity is $O(n)$ as the list nodes are only traversed once.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments