Dada una lista enlazada circular, cuente el número de Nodes en ella. Por ejemplo, la salida es 5 para la siguiente lista.
Utilizamos el concepto utilizado en Circular Linked List | Conjunto 2 (Transversal) . Mientras recorremos, hacemos un seguimiento del recuento de Nodes.
C++
// C++ program to count number of nodes in a circular
// linked list.
#include <bits/stdc++.h>
using namespace std;
/*structure for a node*/
struct Node {
int data;
Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
/* Function to insert a node at the beginning
of a Circular linked list */
struct Node* push(struct Node* last, int data)
{
if (last == NULL) {
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp->data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp->next = last;
return last;
}
// Creating a node dynamically.
struct Node* temp
= (struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp->data = data;
// Adjusting the links.
temp->next = last->next;
last->next = temp;
return last;
}
/* Function to count nodes in a given Circular
linked list */
int countNodes(Node* head)
{
Node* temp = head;
int result = 0;
if (head != NULL) {
do {
temp = temp->next;
result++;
} while (temp != head);
}
return result;
}
/* Driver program to test above functions */
int main()
{
/* Initialize lists as empty */
Node* head = NULL;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
cout << countNodes(head);
return 0;
}
// This code is contributed by anushikaseth
C
// C program to count number of nodes in a circular linked
// list.
#include <stdio.h>
#include <stdlib.h>
/*structure for a node*/
typedef struct Node {
int data;
struct Node* next;
} Node;
/* Function to insert a node at the beginning of a Circular
linked list */
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 linked list is not NULL then set the next of last
* node */
if (*head_ref != NULL) {
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
/* Function to count nodes in a given Circular
linked list */
int countNodes(Node* head)
{
Node* temp = head;
int result = 0;
if (head != NULL) {
do {
temp = temp->next;
result++;
} while (temp != head);
}
return result;
}
/* Driver program to test above functions */
int main()
{
/* Initialize lists as empty */
Node* head = NULL;
push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);
printf("%d", countNodes(head));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to count number of nodes in
// a circular linked list.
class GFG
{
/* ure for a node */
static class Node
{
int data;
Node next;
};
/* Function to insert a node at the beginning
of a Circular linked list */
static Node push( Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
/* If linked list is not null then set
the next of last node */
if (head_ref != null)
{
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
ptr1.next = ptr1; /*For the first node */
head_ref = ptr1;
return head_ref;
}
/* Function to print nodes in a given Circular
linked list */
static int countNodes( Node head)
{
Node temp = head;
int result = 0;
if (head != null)
{
do
{
temp = temp.next;
result++;
} while (temp != head);
}
return result;
}
/* Driver program to test above functions */
public static void main(String args[])
{
/* Initialize lists as empty */
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));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to count number of nodes in # a circular linked list. # structure for a node class Node: def __init__(self, data): self.data = data self.next = None # Function to insert a node at the beginning # of a Circular linked list */ def push(head_ref,data): ptr1 = Node(0) temp = head_ref ptr1.data = data ptr1.next = head_ref # If the linked list is not None then set # the next of last node if (head_ref != None) : while (temp.next != head_ref): temp = temp.next temp.next = ptr1 else: ptr1.next = ptr1 #For the first node */ head_ref = ptr1 return head_ref # Function to print nodes # in a given Circular linked list def countNodes(head): temp = head result = 0 if (head != None) : while True : temp = temp.next result = result + 1 if (temp == head): break return result # Driver Code if __name__=='__main__': # Initialize lists as empty */ head = None head = push(head, 12) head = push(head, 56) head = push(head, 2) head = push(head, 11) print( countNodes(head)) # This code is contributed by Arnab Kundu
C#
// C# program to count number of nodes in
// a circular linked list.
using System;
class GFG
{
/* structure for a node */
public class Node
{
public int data;
public Node next;
};
/* Function to insert a node at the beginning
of a Circular linked list */
static Node push( Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
/* If linked list is not null then set
the next of last node */
if (head_ref != null)
{
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
ptr1.next = ptr1; /*For the first node */
head_ref = ptr1;
return head_ref;
}
/* Function to print nodes in a given Circular
linked list */
static int countNodes( Node head)
{
Node temp = head;
int result = 0;
if (head != null)
{
do
{
temp = temp.next;
result++;
} while (temp != head);
}
return result;
}
/* Driver code */
public static void Main(String []args)
{
/* Initialize lists as empty */
Node head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
Console.Write( countNodes(head));
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// javascript program to count number of nodes in
// a circular linked list. /* ure for a node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/*
* Function to insert a node at the beginning of a Circular linked list
*/
function push(head_ref , data) {
var ptr1 = new Node();
var temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
/*
* If linked list is not null then set the next of last node
*/
if (head_ref != null) {
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
ptr1.next = ptr1; /* For the first node */
head_ref = ptr1;
return head_ref;
}
/*
* Function to print nodes in a given Circular linked list
*/
function countNodes(head) {
var temp = head;
var result = 0;
if (head != null) {
do {
temp = temp.next;
result++;
} while (temp != head);
}
return result;
}
/* Driver program to test above functions */
/* Initialize lists as empty */
var head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
document.write(countNodes(head));
// This code contributed by umadevi9616
</script>
Producción
4
Complejidad de tiempo: O (n), ya que estamos visitando cada Node solo una vez.
Espacio auxiliar: O(1), ya que se utiliza espacio extra constante
Este artículo es una contribución de Rishabh jain . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA