Trouver le «Nième nœud à partir de la fin» d'une liste chaînée

Question

Cela semble renvoyer la bonne réponse, mais je ne suis pas sûr que ce soit vraiment la meilleure façon de procéder. Il semble que je visite les n premiers noeuds trop souvent. Aucune suggestion? Notez que je dois le faire avec une liste unique.

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; 
} 

Answer 1

Une autre façon de le faire sans visiter nœuds est deux fois comme suit:

Créer un tableau vide de taille n, un pointeur dans ce tableau, en commençant à l'index 0, et commencer à itérer depuis le début de la liste chaînée. Chaque fois que vous visitez un noeud, stockez-le dans l'index actuel du tableau et avancez le pointeur du tableau. Lorsque vous remplissez le tableau, enveloppez et remplacez les éléments que vous avez stockés auparavant. Lorsque vous atteignez la fin de la liste, le pointeur pointera sur l'élément n à la fin de la liste.

Mais ce n'est également qu'un algorithme O (n). Ce que vous faites actuellement va bien. Je ne vois aucune raison impérieuse de le changer.

Answer 2

Vous pouvez utiliser une liste à double liaison, qui est une liste chaînée qui stocke également l'adresse de son parent. Transversal est beaucoup plus facile, puisque vous pouvez commencer à la fin et travailler votre chemin vers le début.

Answer 3

Votre temps de fonctionnement est toujours O (n), donc je ne vois pas qu'il y a un problème. Conceptuellement, vous pouvez diviser la liste en deux parties: la partie avant le noeud que vous retournez et la partie après. Une de ces parties devra être marché deux fois. Votre implémentation a choisi la première, à l'avantage de ne pas utiliser de mémoire supplémentaire (autre que quelques variables temporaires). Sinon, vous pouvez créer une pile, parcourir la liste et placer chaque élément dans la pile, puis faire apparaître n éléments. Ensuite, vous marcherez la fin de la liste deux fois, au lieu du début. Cela a l'inconvénient de stocker deux fois la liste en mémoire. (Vous pouvez rendre la pile un peu plus intelligente en ne stockant que n éléments et en les déposant au bas de la pile lorsque de nouveaux sont ajoutés, alors vous utilisez seulement assez d'espace pour stocker n nœuds.)

Je suis en supposant que vous ne pouvez pas effacer la liste en l'inversant en place. Puis c'est la mémoire constante, toujours O (n), marchant encore deux fois à la fin de la liste.

Answer 4

Démarrer deux pointeurs. Déplacez le premier élément N à l'avance, puis déplacez chaque pointeur 1 élément. Lorsque le premier pointeur atteint la fin, le second pointeur donnera la réponse.

EDIT: Oui, c'est à peu près le même code que celui donné dans la question. Mais je pense que le pseudo code le rend plus clair. Pour répondre à la question, il n'y a pas d'autre choix car les premiers éléments N doivent être visités deux fois. Si N est petit cela n'a pas d'importance. Si N est grand alors la deuxième boucle sera petite. Donc, c'est toujours une solution O(n).

Answer 5

Commencez par compter le nombre de nœuds dans la liste. Puis traversez à nouveau, en comptant n moins de nœuds. Encore un algorithme O (n), c'est inévitable.

Answer 6

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; 
} 

Answer 7

J'utilise une variable statique « i » qui sera incrémenté en recul par rapport à la fin de la liste. Comme dans l'énoncé du problème , nous suivrions essentiellement l'élément Nth à partir de la fin de la liste chaînée. La récursivité nous aide à suivre depuis la fin.

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; 
    } 

} 

Answer 8

son très simple .. prendre deux pointeurs p1, p2 début p2 après p1 a parcouru « n » noeuds et laissez-p1 Voyage jusqu'à last.the noeud pointé par p2 sera noeud nième de la dernière

Answer 9

Conserver 2 pointeurs n nœuds à part. Lorsque le 1er pointeur atteint la queue, le second pointeur pointe vers le noeud désiré.

code:

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 

}

Answer 10

Ce code semble être plus clair.

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; 
} 

Answer 11

Utilisez deux pointeur pTemp et NthNode. Initialement, les deux points à tête de noeud de la liste. NthNode commence à se déplacer uniquement après que pTemp a effectué n mouvements. De tous les deux se déplace vers l'avant jusqu'à ce que pTemp atteigne la fin de la liste. Par conséquent, NthNode pointe vers le nième nœud à partir de la fin de la liste chaînée.

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; 
    } 

Référez TextBook: « Structure de données et algorithmes Made Easy en Java »