Dada una lista enlazada y un número n, escriba una función que devuelva el valor en el Node n desde el final de la lista enlazada.
Por ejemplo, si la entrada está debajo de la lista y n = 3, entonces la salida es «B»
Método 1 (Usar la longitud de la lista enlazada):
- Calcular la longitud de la lista enlazada. Sea la longitud len.
- Imprima el (len – n + 1) Node desde el principio de la lista enlazada.
Concepto de puntero doble: el primer puntero se usa para almacenar la dirección de la variable y el segundo puntero se usa para almacenar la dirección del primer puntero. Si deseamos cambiar el valor de una variable por una función, le pasamos un puntero. Y si deseamos cambiar el valor de un puntero (es decir, debería empezar a apuntar a otra cosa), pasamos puntero a puntero.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to find n'th node from // end #include <bits/stdc++.h> using namespace std; // Link list node struct Node { int data; struct Node* next; }; /* Function to get the nth node from the last of a linked list*/ void printNthFromLast(struct Node* head, int n) { int len = 0, i; struct Node* temp = head; // count the number of nodes in // Linked List while (temp != NULL) { temp = temp->next; len++; } // check if value of n is not // more than length of the // linked list if (len < n) return; temp = head; // get the (len-n+1)th node from // the beginning for (i = 1; i < len - n + 1; i++) temp = temp->next; cout << temp->data; return; } void push(struct Node** head_ref, int new_data) { // Allocate node struct Node* new_node = new 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; } // Driver Code int main() { // Start with the empty list struct Node* head = NULL; // Create linked 35->15->4->20 push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 35); printNthFromLast(head, 4); return 0; }
Producción:
35
C++
void printNthFromLast(struct Node* head, int n) { int i = 0; if (head == NULL) return; printNthFromLast(head->next, n); if (++i == n) cout<<head->data; }
Complejidad de tiempo: O(n) donde n es la longitud de la lista enlazada.
Método 2 (Usar dos punteros)
Mantener dos punteros: puntero de referencia y puntero principal. Inicialice tanto los punteros de referencia como los principales en head. Primero, mueva el puntero de referencia a n Nodes desde la cabeza. Ahora mueva ambos punteros uno por uno hasta que el puntero de referencia llegue al final. Ahora el puntero principal apuntará al Node n desde el final. Devuelve el puntero principal.
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// Simple C++ program to // find n'th node from end #include<bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to get the nth node from the last of a linked list*/ void printNthFromLast(struct Node *head, int n) { struct Node *main_ptr = head; struct Node *ref_ptr = head; int count = 0; if(head != NULL) { while( count < n ) { if(ref_ptr == NULL) { printf("%d is greater than the no. of " "nodes in list", n); return; } ref_ptr = ref_ptr->next; count++; } /* End of while*/ if(ref_ptr == NULL) { head = head->next; if(head != NULL) printf("Node no. %d from last is %d ", n, main_ptr->data); } else { while(ref_ptr != NULL) { main_ptr = main_ptr->next; ref_ptr = ref_ptr->next; } printf("Node no. %d from last is %d ", n, main_ptr->data); } } } // Function to push void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = new 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; } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 35); printNthFromLast(head, 4); }
Node no. 4 from last is 35
Complejidad de tiempo: O(n) donde n es la longitud de la lista enlazada.
Complejidad espacial : O(1) ya que usa espacio constante
Consulte el artículo completo sobre Programa para el Node n desde el final de una lista vinculada 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