Count nodes in Circular linked list
Last Updated :
28 Feb, 2023
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
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...