How to count nodes in 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 is very useful in solving various problems.

Understanding the problem

Let's suppose we have a circular linked list, and we have to count its nodes. This might seem tricky, as there is no indication of the end of the list when we only have a head pointer, or of the start when we have a tail pointer.

Solution

One possible solution to this problem is to:

Traverse the list using a temporary variable, starting from the node after the head.
Keep a count variable that increments through each iteration of the traversal.
Stop when the temporary variable becomes equal to the head pointer.

Code

The following is a program to calculate the number of nodes in a circular linked list:

#include <iostream>
using namespace std;
// The structure for the linked list node
struct node {
	int data;
	node* next;
	node(int x){
		data = x;
		next = nullptr;
	}
};
struct node* insertnode(struct node* ptr, int val){
	if (ptr == nullptr) {
		struct node* temp	= (struct node*)malloc(sizeof(struct node));
		temp->data = val;
		ptr = temp;
		temp->next = ptr;
		return ptr;
	}
	struct node* temp = (struct node*)malloc(sizeof(struct node));
	temp->data = val;
	temp->next = ptr->next;
	ptr->next = temp;
	return ptr;
}
// The function to count nodes
int countnodes(node* head){
	node* temp = head;
	int count = 0;
	if (head != nullptr) {
		do {
            temp = temp->next;
            count++;
        } while (temp != head);
	}
	return count;
}
int main(){
	node* head = nullptr;
	head = insertnode(head, 1);
	head = insertnode(head, 2);
	head = insertnode(head, 3);
	head = insertnode(head, 4);
	head = insertnode(head, 5);
	cout << countnodes(head);
	return 0;
}

Explanation

Lines 5–12: A node struct is formed, which is the building block of our list. It contains a data integer and a next node pointer.

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

Lines 31–42: This is our countnodes function where we traverse each node starting, from the node next to the head, and keep a counter variable. It stops looping until the temp pointer reaches back to the head.

Lines 44–53: The main function calls the insertnode function to add nodes, and the countnodes function to count the nodes.

Time complexity

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

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources