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.
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.
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.
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 nodestruct 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 nodesint 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;}
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.
The above code's time complexity is
Free Resources