22 votes

Trouver le "n-ième nœud à partir de la fin" d'une liste chaînée

Cela semble être de retour la bonne réponse, mais je ne sais pas si c'est vraiment la meilleure façon d'aborder les choses. Il me semble que je vais visiter les n premiers nœuds de trop nombreuses fois. Toutes les suggestions? Remarque que j'ai à faire avec une seule liste liée.

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

14voto

Mark Byers Points 318575

Une autre façon de le faire sans une visite de nœuds à deux reprises est comme suit:

Créer un tableau vide de taille n, un pointeur vers ce tableau commençant à l'indice 0, et commencer à parcourir depuis le début de la liste chaînée. Chaque fois que vous visitez un nœud de le stocker dans le courant de l'indice de la matrice et avance le pointeur sur le tableau. Lorsque vous remplissez le tableau, enrouler autour de et de remplacer les éléments que vous avez stocké. Lorsque vous atteignez la fin de la liste, le pointeur pointe sur l'élément n à partir de la fin de la liste.

Mais c'est aussi juste un algorithme O(n). Ce que vous faites actuellement est très bien. Je vois aucune raison de le changer.

7voto

fastcodejava Points 22174

Démarrer une deux pointeurs. Déplacer le premier N éléments à l'avance, puis déplacez le pointeur de 1 élément. Lorsque le premier pointeur atteint la fin, le deuxième pointeur de donner la réponse.

EDIT : Oui, c'est à peu près le même code que donné dans la question. Mais j'ai l'impression que le pseudo-code de la rendre plus claire. Pour répondre à la question, il n'y a pas d'autres aller en tant que premier N éléments doivent être visité à deux reprises. Si N est petit il n'a pas d'importance. Si N est grande alors la deuxième boucle sera petit. Il est donc toujours un O(n) de la solution.

6voto

PCB Points 61

Maintenir 2 pointeurs de n noeuds en dehors. Lors de la 1ère pointeur atteint la queue, le deuxième pointeur pointera vers le nœud 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

}

4voto

sanjay Points 41

Je suis l'aide d'une variable statique " je " qui sera incrémentée tout retour en arrière à partir de la fin de la Liste. Comme dans le énoncé du problème, on serait essentiellement le suivi de la Nième élément à partir de la fin de la liste liée. La récursivité nous permet de suivre à partir de 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; 
     }

}

1voto

Eric Warmenhoven Points 2334

Votre temps de course est toujours en O(n), donc je ne vois pas qu'il y a un problème avec elle.

Conceptuellement, vous pouvez diviser la liste en deux parties: la partie avant du nœud que vous êtes de retour, et la partie d'après. L'une de ces pièces devront être parcouru à deux reprises. Votre application a choisi la première, à l'avantage de ne pas supplémentaire de l'utilisation de la mémoire (autre qu'un couple de variables temporaires).

Alternativement, vous pouvez créer une pile, parcourir la liste et mettre chaque élément dans la pile, puis pop off n éléments. Alors vous seriez en marche à la fin de la liste deux fois, au lieu du début. Ceci a l'inconvénient de stockage de la liste en mémoire deux fois. (Vous pourriez faire de la pile un peu plus intelligent en ne sauvegardant que les n éléments et de les déposer en bas de la pile et de nouveaux sont ajoutés; alors vous êtes seulement en utilisant suffisamment d'espace pour stocker les n Noeuds.)

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

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X