Approach
In the below code, our purpose is to count the number of duplicates, and we achieve this by using a hash set. The use of a hash set (unordered_set in C++ STL) is generally preferred because of its O(1) retrieval and insertion time on average.
The algorithm requires us to traverse through the circular linked list once and check if that element is present in the hash set for each iteration. If the element exists in the hash set, then it’s a duplicate, and we increase the duplicate count; otherwise, we insert the element into the hash set as it hadn’t occurred before.
After having traversed through all the elements of the hash set, we end up with the count of the duplicate elements in the circular linked list, and we print that as the final result.
Code in C++
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
class Node{
public:
int val;
Node *next;
Node(int x){
val = x;
next = NULL;
}
};
int main(){
// let us store all the content in the below vector into the circular linked list
vector<int> data = {10, 1, 1, 7, 5, 5, 5};
Node *head = new Node(data[0]);
Node *temp = head;
for(int i = 1; i < data.size(); i++){
temp->next = new Node(data[i]);
temp = temp->next;
}
temp->next = head; // the end element points back to the head, making it a circular linked list
//from here on we have the logic for counting the duplicates
int duplicates = 0;
unordered_set<int> s;
Node *loop_var = head;
do{
if(s.find(loop_var->val) != s.end()){
// if a previous occurence is found
duplicates += 1;
}
else{
s.insert(loop_var->val);
}
loop_var = loop_var->next;
}
while(loop_var != head);
// print the total duplicates
// [10, 1, 1 <-, 7, 5, 5 <-, 5 <-]
// I have put arrows next to the duplicates and we expect an output of 3 for the given input
cout << duplicates << endl;
}

You can also try this code with Online C++ Compiler
Run Code
Output:
3
Time Complexity
The time complexity is O(N), as we traverse each element of the list once, and the retrieval from the unordered_set is O(1) on average for random data. (Do note, however, that unordered_set can have O(N) retrieval and insertion in a worst-case under particular inputs.)
Space Complexity
The space complexity is O(N) because of the unordered_set data structure, where we store elements to check for their earlier occurrence in the circular linked list.
Also read - Merge sort in linked list
Frequently Asked Questions
What are the advantages of learning about circular linked lists?
It can implement circular linked list queues and various advanced data structures such as Fibonacci heaps. They can also be helpful in multiple other situations repeatedly requiring iteration over the same data.
Difference between unordered_set and set in C++?
The set data structure is usually implemented using a red-black tree (read more about it here). The unordered_set, however, is implemented using a hash table and hence offers an average O(1) retrieval and insertion. In contrast,a set data structure takes O(log(n)) for retrieving and inserting an element.
Is unordered_set always better than set?
No, the unordered_set will usually work well with random data and give O(1) retrieval and insertion on average. Still, in case of excessive collisions (which can be the case for some specific inputs, depending on the hash function), our retrieval and insertion may become O(N).
Conclusion
The article helps you understand and implement your knowledge of circular linked lists and C++ STL. I also recommend checking the program for multiple inputs to understand the process better if you still have some doubts.
In the code, you may have noticed my use of a do-while loop instead of a while loop. I encourage you to try the same problem with a while loop, observe the difference in implementation, and decide if it’s better and easier to use a do-while loop in the case of circular linked lists.
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
To study more about Linked Lists, refer to Applications Of Linked Lists.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Cheers!