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 Resources