.png)
Count Nodes in a Circular Linked List
Problem Statement
Given the head of a circular linked list, write a program to count the total number of nodes present in the list.
In a circular linked list, the last node points back to the head node instead of pointing to NULL. Due to this circular nature, special care must be taken to avoid infinite traversal.
Example
Input
Circular Linked List:
10 → 20 → 30 → 40 → back to 10
Output
Number of nodes = 4
Approach 1: Simple Traversal from Head
Approach Explanation
Start traversal from the head node and keep counting nodes until the traversal reaches the head again. Since a circular linked list loops back to the head, encountering the head node again indicates that all nodes have been counted.
Algorithm
- If head == NULL, return 0.
- Initialize count = 0.
- Set current = head.
- Traverse the list:
- Increment count.
- Move current = current.next.
- Stop when current == head.
- Return count.
Time Complexity
- Best Case: O(1)
- Worst Case: O(n)
- Average Case: O(n)
Space Complexity
- O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
int countNodes(struct Node* head) {
if (head == NULL)
return 0;
int count = 0;
struct Node* current = head;
do {
count++;
current = current->next;
} while (current != head);
return count;
}
// Helper to create circular linked list
struct Node* createCLL() {
struct Node *head = NULL, *temp = NULL, *prev = NULL;
int arr[] = {10, 20, 30, 40};
int n = 4;
for(int i = 0; i < n; i++) {
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = arr[i];
temp->next = NULL;
if(head == NULL)
head = temp;
else
prev->next = temp;
prev = temp;
}
prev->next = head; // make circular
return head;
}
int main() {
struct Node* head = createCLL();
printf("Number of nodes = %d", countNodes(head));
return 0;
}
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
int countNodes(Node* head) {
if (head == NULL)
return 0;
int count = 0;
Node* current = head;
do {
count++;
current = current->next;
} while (current != head);
return count;
}
// Helper function
Node* createCLL() {
int arr[] = {10, 20, 30, 40};
int n = 4;
Node* head = NULL;
Node* prev = NULL;
for(int i = 0; i < n; i++) {
Node* temp = new Node(arr[i]);
if(head == NULL)
head = temp;
else
prev->next = temp;
prev = temp;
}
prev->next = head; // circular
return head;
}
int main() {
Node* head = createCLL();
cout << "Number of nodes = " << countNodes(head);
return 0;
}Java Implementation
static int countNodes(Node head) {
if (head == null)
return 0;
int count = 0;
Node current = head;
do {
count++;
current = current.next;
} while (current != head);
return count;
}
Python Implementation
def count_nodes(head):
if head is None:
return 0
count = 0
current = head
while True:
count += 1
current = current.next
if current == head:
break
return count
JavaScript Implementation
function countNodes(head) {
if (head === null)
return 0;
let count = 0;
let current = head;
do {
count++;
current = current.next;
} while (current !== head);
return count;
}
Output
Number of nodes = 4Approach 2: Using Floyd’s Cycle Detection Algorithm
This approach first detects the cycle using Floyd’s Algorithm. Once a cycle is detected, the number of nodes in the cycle is counted by traversing the cycle until the pointer reaches the same node again.
Algorithm
- If head == NULL, return 0.
- Use two pointers:
- slow moves one step.
- fast moves two steps.
- When slow == fast, a cycle is detected.
- Initialize count = 1.
- Move one pointer around the loop until it meets the same pointer again.
- Increment count for each step.
- Return count.
Time Complexity
- O(n)
Space Complexity
- O(1)
C++ Implementation
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
int countNodes(Node* head) {
if (head == NULL)
return 0;
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
int count = 1;
Node* temp = slow->next;
while (temp != slow) {
count++;
temp = temp->next;
}
return count;
}
}
return 0;
}
// Helper
Node* createCLL() {
int arr[] = {10, 20, 30, 40};
int n = 4;
Node* head = NULL;
Node* prev = NULL;
for(int i = 0; i < n; i++) {
Node* temp = new Node(arr[i]);
if(head == NULL)
head = temp;
else
prev->next = temp;
prev = temp;
}
prev->next = head;
return head;
}
int main() {
Node* head = createCLL();
cout << "Number of nodes = " << countNodes(head);
return 0;
}
Java Implementation
static int countNodes(Node head) {
if (head == null)
return 0;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
int count = 1;
Node temp = slow.next;
while (temp != slow) {
count++;
temp = temp.next;
}
return count;
}
}
return 0;
}
Python Implementation
def count_nodes(head):
if head is None:
return 0
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
count = 1
temp = slow.next
while temp != slow:
count += 1
temp = temp.next
return count
return 0
JavaScript Implementation
function countNodes(head) {
if (head === null) return 0;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let count = 1;
let temp = slow.next;
while (temp !== slow) {
count++;
temp = temp.next;
}
return count;
}
}
return 0;
}
Output
Number of nodes = 4Comparison of Approaches
| Approach | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| Traversal from Head | O(n) | O(1) | Pure circular linked list |
| Floyd’s Algorithm | O(n) | O(1) | Cycle detection based |
Edge Cases
- Empty linked list
- Single node circular list
- Large circular linked list
Conclusion
Counting nodes in a circular linked list can be efficiently achieved using simple traversal or Floyd’s cycle detection algorithm. The traversal approach is straightforward when the list is known to be circular, while Floyd’s algorithm is useful when circularity must also be validated.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
