'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Dec 19, 2023

Count Duplicates in Circular Linked List

0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
Earn badges and level up
Linked List


The following article aims to familiarise you with using a circular linked list (if this is a new topic for you, refer to the article here) data structure and practice its use in real questions to build and strengthen your concepts. The following question explores how we can traverse a circular linked list and find the count of duplicate elements using a hash set.

Problem Statement

Count the number of duplicate elements in a circular linked list, i.e., elements that have already occurred before, and print the count as the final result.

For example,

Input 1: [1, 2, 3, 1, 2]

In the above input [1, 2, 3, 1 <-, 2 <-], the numbers marked by arrows are duplicates.

Output 1: 2


Input 2: [5, 5, 5, 5]

In the above input [5, 5 <-, 5 <-, 5 <-], similar to input 1, arrows mark the duplicate elements.

Output 2: 3

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job


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{
   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;
      if(s.find(loop_var->val) != s.end()){
          // if a previous occurence is found
          duplicates += 1;
      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;



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).


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.


Previous article
Deletion in a Circular Linked List
Next article
Circular Linked List Traversal
Guided path
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
Earn badges and level up
Live masterclass