Given a circular linked list, count the number of nodes in it. For example, the output is 5 for the below list.
Approach: We use the concept used in Circular Linked List | Set 2 (Traversal). While traversing, we keep track of the count of nodes.
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
struct Node* push(struct Node* last, int data)
{
if (last == NULL) {
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
last = temp;
temp->next = last;
return last;
}
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = last->next;
last->next = temp;
return last;
}
int countNodes(Node* head)
{
Node* temp = head;
int result = 0;
if (head != NULL) {
do {
temp = temp->next;
result++;
} while (temp != head);
}
return result;
}
int main()
{
Node* head = NULL;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
cout << countNodes(head);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
void push(Node** head_ref, int data)
{
Node* ptr1 = (Node*)malloc(sizeof(Node));
Node* temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
if (*head_ref != NULL) {
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1;
*head_ref = ptr1;
}
int countNodes(Node* head)
{
Node* temp = head;
int result = 0;
if (head != NULL) {
do {
temp = temp->next;
result++;
} while (temp != head);
}
return result;
}
int main()
{
Node* head = NULL;
push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);
printf("%d", countNodes(head));
return 0;
}
|
Java
import java.util.*;
import java.io.*;
public class GFG
{
static class Node
{
int data;
Node next;
};
static Node push( Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
if (head_ref != null)
{
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
static int countNodes( Node head)
{
Node temp = head;
int result = 0;
if (head != null)
{
do
{
temp = temp.next;
result++;
} while (temp != head);
}
return result;
}
public static void main(String args[])
{
Node head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
System.out.printf("%d", countNodes(head));
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
def push(head_ref,data):
ptr1 = Node(0)
temp = head_ref
ptr1.data = data
ptr1.next = head_ref
if (head_ref != None) :
while (temp.next != head_ref):
temp = temp.next
temp.next = ptr1
else:
ptr1.next = ptr1
head_ref = ptr1
return head_ref
def countNodes(head):
temp = head
result = 0
if (head != None) :
while True :
temp = temp.next
result = result + 1
if (temp == head):
break
return result
if __name__=='__main__':
head = None
head = push(head, 12)
head = push(head, 56)
head = push(head, 2)
head = push(head, 11)
print( countNodes(head))
|
C#
using System;
class GFG
{
public class Node
{
public int data;
public Node next;
};
static Node push( Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
if (head_ref != null)
{
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
static int countNodes( Node head)
{
Node temp = head;
int result = 0;
if (head != null)
{
do
{
temp = temp.next;
result++;
} while (temp != head);
}
return result;
}
public static void Main(String []args)
{
Node head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
Console.Write( countNodes(head));
}
}
|
Javascript
<script>
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
function push(head_ref , data) {
var ptr1 = new Node();
var temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
if (head_ref != null) {
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
function countNodes(head) {
var temp = head;
var result = 0;
if (head != null) {
do {
temp = temp.next;
result++;
} while (temp != head);
}
return result;
}
var head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
document.write(countNodes(head));
</script>
|
Time Complexity: O(n), As we are visiting every node just once.
Auxiliary Space: O(1), As constant extra space is used
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!