Introduction
We'll learn how to compute the number of nodes in a circular linked list in this article.
A circular linked list is one in which the start and last nodes are connected to create a circle. The last node's address is equal to the first node's address.
Problem Statement
The aim is to calculate the number of nodes in a circular linked list.
Example
Input 1
nodes-: 27, 18, 23, 5, 8, 12
Output
total number of nodes is-: 6
Input 2
nodes-: 1, 5, 7, 14, 16, 22, 19, 8, 9,
Output
total number of nodes is-: 9
Algorithm
- Make a singly linked list structure that includes the node's address and data.
- Make a push() function to push data into the node.
- To convert a singly linked list into a circular linked list, store the address of the first node in the last node.
- Create a count function that counts all of the nodes in a circular linked list.
Implementation
//Count the number of nodes in a circular linked list with a C program.
#include <stdio.h>
#include <stdlib.h>
/*a node's structure*/
struct Node {
int data;
struct Node* next;
};
/*Insert a node at the start of a circular linked list with this function. */
void push(struct Node** head_ref, int data)
{
struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
struct Node* temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
/* Set the next of the final node if the linked list is not NULL. */
if (*head_ref != NULL) {
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
} else
ptr1->next = ptr1; /*For the initial node */
*head_ref = ptr1;
}
/* Nodes in a Circular linked list are printed using this function.*/
int countNodes(struct Node* head)
{
struct Node* temp = head;
int result = 0;
if (head != NULL) {
do {
temp = temp->next;
result++;
} while (temp != head);
}
return result;
}
/* Driver program */
int main()
{
/* Initialize lists as empty */
struct Node* head = NULL;
push(&head, 9);
push(&head, 18);
push(&head, 27);
push(&head, 45);
printf("number of nodes are:%d", countNodes(head));
return 0;
}
Also read - Merge sort in linked list
Output:
number of nodes are: 4
Complexity Analysis
Time Complexity: O(N) Because we have to traverse the whole list.
Space Complexity: The space complexity is O(1) as we are not using any auxiliary space.
Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.