c++ - node - Encontrar el "Nth nodo desde el final" de una lista enlazada
singly linked list java (11)
Este código parece ser más claro.
public Node<T> findNthNodeFromLast(int n) {
Node<T> current = head;
Node<T> findElement = head;
int length = 0;
while (current != null && current.next != null) {
length++;
if (length >= n) {
findElement = findElement.next;
}
current = current.next;
}
return findElement;
}
Esto parece estar devolviendo la respuesta correcta, pero no estoy seguro de si esta es realmente la mejor manera de hacer las cosas. Parece que estoy visitando los primeros nodos muchas veces. ¿Alguna sugerencia? Tenga en cuenta que tengo que hacer esto con una lista enlazada individualmente.
Node *findNodeFromLast( Node *head, int n )
{
Node *currentNode;
Node *behindCurrent;
currentNode = head;
for( int i = 0; i < n; i++ ) {
if( currentNode->next ) {
currentNode = currentNode->next;
} else {
return NULL;
}
}
behindCurrent = head;
while( currentNode->next ) {
currentNode = currentNode->next;
behindCurrent = behindCurrent->next;
}
return behindCurrent;
}
Estoy usando una variable estática ''i'' que se incrementará mientras retrocede desde el final de la Lista. Al igual que en la declaración del problema, básicamente rastrearíamos el elemento Nth desde el final de la lista enlazada. La recursión nos ayuda a rastrear desde el final.
static int i;
public static void NthToLast(LinkedListNode head, int n)
{
if (head == null)
return;
NthToLast(head.Next, n);
i++;
if (n == i)
{
Console.WriteLine("Mth to last" + head.Data);
return;
}
}
Iniciar un dos punteros. Mueva el primero uno de los elementos N hacia adelante y luego mueva cada elemento del puntero 1. Cuando el primer puntero llega al final, el segundo puntero dará la respuesta.
EDIT : Sí, es más o menos el mismo código que se da en la pregunta. Pero siento que el pseudo código lo hace más claro. Para responder a la pregunta, no hay otra opción, ya que los primeros N elementos deben visitarse dos veces. Si N es pequeño no importa. Si N es grande, entonces el segundo bucle será pequeño. Así que siempre es una solución O(n) .
Mantener 2 punteros n nodos separados. Cuando el primer puntero llegue a la cola, el segundo apuntará al nodo deseado.
Código:
typedef struct _node //define the list node
{
int i;
struct _node *next;
} Node;
Node * findNode(Node *listHead, int n)
{
Node *ptr1, *ptr2; // we need 2 pointers
ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially
while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
{
if(n > 0)
{
ptr1 = ptr1->next; //increment only the 1st pointer
n--;
}
else
{
ptr1 = ptr1->next; //increment both pointers
ptr2 = ptr2->next;
}
}
return ptr2; //now return the ptr2 which points to the nth node from the tail
}
Otra forma de hacerlo sin visitar los nodos dos veces es la siguiente:
Cree una matriz vacía de tamaño n, un puntero en esta matriz que comienza en el índice 0, y comience a iterar desde el principio de la lista enlazada. Cada vez que visite un nodo, guárdelo en el índice actual de la matriz y avance el puntero de la matriz. Cuando llene la matriz, envuelva y sobrescriba los elementos que almacenó anteriormente. Cuando llegue al final de la lista, el puntero apuntará al elemento n desde el final de la lista.
Pero esto también es solo un algoritmo O (n). Lo que estás haciendo actualmente está bien. No veo ninguna razón convincente para cambiarlo.
Podría usar una lista doblemente vinculada, que es una lista vinculada que también almacena la dirección de su padre. Transversal es mucho más fácil, ya que puede comenzar por el final y abrirse camino hacia el principio.
Primero cuente el número de nodos en la lista. Luego atraviesa de nuevo, contando n nodos menos. Todavía un algoritmo O (n), eso es inevitable.
Su tiempo de ejecución sigue siendo O (n), por lo que no veo que haya ningún problema con él.
Conceptualmente, puede dividir la lista en dos partes: la parte anterior al nodo que está devolviendo y la parte posterior. Una de estas partes tendrá que ser caminada dos veces. Su implementación ha elegido la primera, con la ventaja de que no se usa memoria adicional (aparte de un par de variables temporales).
Alternativamente, puede crear una pila, recorrer la lista y colocar cada elemento en la pila, y luego quitar n elementos. Entonces estarías caminando el final de la lista dos veces, en lugar del principio. Esto tiene la desventaja de almacenar la lista en la memoria dos veces. (Podría hacer que la pila sea un poco más inteligente si solo almacena n elementos y los suelta de la parte inferior de la pila a medida que se agregan nuevos; entonces, solo está utilizando el espacio suficiente para almacenar n nodos)
Supongo que no puedes eliminar la lista invirtiéndola en su lugar. Entonces es una memoria constante, todavía O (n), aún caminando el final de la lista dos veces.
Utilice dos punteros pTemp y NthNode. Inicialmente, ambos puntos apuntan al nodo principal de la lista. NthNode comienza a moverse solo después de que pTemp hizo n movimientos. A partir de los dos se avanza hasta que pTemp llega al final de la lista. Como resultado, NthNode apunta al nth nodo desde el final de la lista enlazada.
public ListNode NthNodeFromEnd(int n){
ListNode pTemp = head, NthNode = null;
for(int count=1; count<n;count++){
if(pTemp!=null){
pTemp = pTemp.getNext();
}
}
while(pTemp!=null){
if(NthNode==null){
NthNode = head;
}
else{
NthNode = NthNode.getNext();
}
pTemp = pTemp.getNext();
}
if(NthNode!=null){
NthNode = NthNode.getNext();
return NthNode;
}
return null;
}
Consulte el libro de texto: "Estructura de datos y algoritmos simplificados en Java"
es muy simple ... tome dos punteros p1, p2 comience p2 después de que p1 haya viajado ''n'' nodos y deje que p1 viaje hasta el último.
Node* fetchNNodeFrmLast(int arg)
{
Node *temp = head;
Node *nNode = head;
if(head == NULL || arg <= 0)
{
Printf("Either head is null or invalid number entered");
return;
}
while(temp != NULL)
{
temp = temp->next;
if(arg > 1)
{
arg--;
continue;
}
nNode = nNode->next;
}
return nNode;
}