Escriba una función para contar el número de Nodes en una lista enlazada simple dada.
Por ejemplo, la función debería devolver 5 para la lista enlazada 1->3->1->2->1.
Solución iterativa:
1) Initialize count as 0
2) Initialize a node pointer, current = head.
3) Do following while current is not NULL
a) current = current -> next
b) count++;
4) Return count
A continuación se muestra la implementación iterativa del algoritmo anterior para encontrar el recuento de Nodes en una lista de enlaces individuales dada.
C
// Iterative C program to find length or count
// of nodes in a linked list
#include<stdio.h>
#include<stdlib.h>
// Link list node
struct Node
{
int data;
struct Node* next;
};
/* Given a reference (pointer to pointer) to
the head of a list and an int, push a new
node on the front of the list. */
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// Put in the data
new_node->data = new_data;
// Link the old list off the new node
new_node->next = (*head_ref);
// Move the head to point to the new node
(*head_ref) = new_node;
}
// Counts no. of nodes in linked list
int getCount(struct Node* head)
{
// Initialize count
int count = 0;
// Initialize current
struct Node* current = head;
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}
// Driver code
int main()
{
// Start with the empty list
struct Node* head = NULL;
// Use push() to construct list
// 1->2->1->3->1
push(&head, 1);
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 1);
// Check the count function
printf("count of nodes is %d",
getCount(head));
return 0;
}
Producción:
count of nodes is 5
Complejidad de tiempo: O(n), donde n representa la longitud de la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
¡ Consulte el artículo completo sobre Buscar la longitud de una lista vinculada (iterativa y recursiva) para obtener más detalles!
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