Comment trouver le n-ième élément de la fin d'une seule liste liée?

la fonction suivante essaie de trouver l'élément nth à dernier d'une liste mono-liée.

par exemple:

Si les éléments sont 8->10->5->7->2->1->5->4->10->10 , alors le résultat est 7th au dernier noeud est 7 .

est-ce que quelqu'un peut m'aider sur la façon dont ce code fonctionne ou y a-t-il une meilleure et plus simple approche?

LinkedListNode nthToLast(LinkedListNode head, int n) {
  if (head == null || n < 1) {
    return null;
  }

  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
    if (p2 == null) {
      return null; // not found since list size < n
    }
    p2 = p2.next;
  }

  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}
57
demandé sur theIV 2010-04-08 12:03:56

26 réponses

votre algorithme fonctionne d'abord en créant des références à deux noeuds de votre liste liée qui sont séparés par N noeuds. Ainsi, dans votre exemple, si N est 7, alors il va mettre p1 à 8 et p2 à 4.

il avancera ensuite chaque référence de noeud au prochain noeud de la liste jusqu'à ce que p2 atteigne le dernier élément de la liste. Encore une fois, dans votre exemple, ce sera quand p1 est 5 et p2 est 10. À ce stade, p1 se réfère au nième au dernier élément de la liste (par la propriété que ils sont N noeuds en dehors).

34
répondu Eric 2015-09-28 11:15:45

la clé de cet algorithme est de définir deux pointeurs p1 et p2 séparés par des noeuds n-1 initialement donc nous voulons p2 pour pointer vers le noeud (n-1)th du début de la liste puis nous déplacer p2 jusqu'à ce qu'il atteigne le noeud last de la liste. Une fois que p2 atteint la fin de la liste p1 pointera vers le nième noeud à partir de la fin de la liste.

j'ai mis l'explication en ligne comme commentaires. Espérons qu'il aide:

// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
  // If list does not exist or if there are no elements in the list,return NULL
  if (head == null || n < 1) {
    return null;
  }

  // make pointers p1 and p2 point to the start of the list.
  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
  // so we want p2 to point to the (n-1)th node from the start of the list
  // then we move p2 till it reaches the last node of the list. 
  // Once p2 reaches end of the list p1 will be pointing to the nth node 
  // from the end of the list.

  // loop to move p2.
  for (int j = 0; j < n - 1; ++j) { 
   // while moving p2 check if it becomes NULL, that is if it reaches the end
   // of the list. That would mean the list has less than n nodes, so its not 
   // possible to find nth from last, so return NULL.
   if (p2 == null) {
       return null; 
   }
   // move p2 forward.
   p2 = p2.next;
  }

  // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
  // till p2 reaches the last node in the list.
  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

   // at this point p2 has reached the last node in the list and p1 will be
   // pointing to the nth node from the last..so return it.
   return p1;
 }

nous pouvons aussi définir p1 et p2 séparés par n noeuds au lieu de (n-1) et puis déplacer p2 jusqu'à la fin de la liste au lieu de se déplacer jusqu'au dernier noeud:

LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j < n ; ++j) { // make then n nodes apart.
    if (p2 == null) {
        return null;
    }
    p2 = p2.next;
}
while (p2 != null) { // move till p2 goes past the end of the list.
    p1 = p1.next;
    p2 = p2.next;
}
return p1;
61
répondu codaddict 2010-04-09 06:42:45

Que pensez-vous de cette approche?

  1. Comte de la longueur de la linkedlist.
  2. Nœud Réel indice de la tête = linkedlist longueur - index donné;
  3. écrivez une fonction à travesre de la tête et obtenez le noeud à l'index ci-dessus.
9
répondu Pritam Karmakar 2010-08-14 20:20:24
//this  is the recursive solution


//initial call
find(HEAD,k);

// main function
void find(struct link *temp,int k)
{  
 if( temp->next != NULL)
   find( temp->next, k);
 if((c++) == k)       // c is initially declared as 1 and k is the node to find from last.
  cout<<temp->num<<' ';
}
7
répondu dekontj 2012-06-12 13:20:17

il y a déjà beaucoup de réponses ici, mais elles marchent toutes deux fois dans la liste (de façon séquentielle ou en parallèle) ou utilisent beaucoup de stockage supplémentaire.

vous pouvez le faire en parcourant la liste juste une fois (plus un petit peu) en utilisant un espace supplémentaire constant:

Node *getNthFromEnd(Node *list, int n) {

    if (list == null || n<1) {
        return null; //no such element
    }

    Node *mark1 = list, *mark2 = list, *markend = list;
    int pos1 = 0, pos2 = 0, posend = 0;

    while (markend!=null) {
        if ((posend-pos2)>=(n-1)) {
            mark1=mark2;
            pos1=pos2;
            mark2=markend;
            pos2=posend;
        }
        markend=markend->next;
        ++posend;
    }
    if (posend<n) {
        return null; //not enough elements in the list
    }

    //mark1 and mark2 are n-1 elements apart, and the end is at least
    //1 element after mark2, so mark1 is at least n elements from the end

    while((posend - pos1) > n) {
      mark1 = mark1->next;
      ++pos1;
    }
    return mark1;
}

Cette version utilise 2 extra pointeurs ne moins de N+n traversals, où N est la longueur de la liste et n est l'argument.

si vous utilisez M pointeurs supplémentaires, vous pouvez obtenir que jusqu'à N+ceil(n/(M-1)) (et vous devez les stocker dans un tampon circulaire)

3
répondu Matt Timmermans 2016-03-30 01:15:32

puisque cela ressemble à des devoirs, je préfère vous aider à vous aider vous-même au lieu de donner une solution réelle.

je vous suggère d'exécuter ce code sur un petit échantillon de données. Utilisez votre débogueur pour exécuter les lignes étape par étape (vous pouvez définir un point de rupture au début de la fonction). Cela devrait vous donner une idée du fonctionnement du code.

vous pouvez aussi Console.WriteLine() pour les variables de production d'intérêt.

2
répondu mafu 2010-04-08 08:16:00

juste une autre solution à ce problème. Bien que la complexité temporelle reste la même, ce code réalise la solution en une seule boucle.

public Link findKthElementFromEnd(MyLinkedList linkedList, int k)
    {
        Link current = linkedList.getFirst();//current node
        Link currentK = linkedList.getFirst();//node at index k

        int counter = 0;

        while(current.getNext()!=null)
        {
            counter++;

            if(counter>=k)
            {
                currentK = currentK.getNext();
            }

            current = current.getNext();
        }

        //reached end
        return currentK;
    }
2
répondu sunsin1985 2013-03-31 14:05:54

inversez simplement la liste de liens dans le temps linéaire et trouvez l'élément kth. Il fonctionne toujours en temps linéaire.

2
répondu Nithin 2013-10-29 08:03:50

vous pouvez simplement boucler la boucle à travers la linkedlist et obtenir la taille. Une fois que vous avez la taille, vous pouvez trouver le n'ème terme dans 2n qui est O(n) still.

public T nthToLast(int n) {
    // return null if linkedlist is empty
    if (head == null) return null;

    // declare placeholder where size of linkedlist will be stored
    // we are hoping that size of linkedlist is less than MAX of INT
    int size = 0;

    // This is O(n) for sure
    Node i = head;
    while (i.next != null) {
        size += 1;
        i = i.next;
    }

    // if user chose something outside the size of the linkedlist return null
    if (size < n)
        return null;

    // This is O(n) if n == size
    i = head;
    while(size > n) {
        size--;
        i = i.next;
    }

    // Time complexity = n + n = 2n
    // therefore O(n)

    return i.value;
}
2
répondu Y_Y 2016-07-30 02:07:42

j'ai une solution récursive à un autre thread dans StackOverflow ici

1
répondu sanjay 2017-05-23 11:47:05

Non, tu ne sais pas la longueur de la linkedlist ... Vous devrez traverser la fois pour obtenir la longueur de la likedlist de sorte que votre approche est peu efficace;

1
répondu CodeR 2012-02-02 22:02:30

nous prenons ici deux pointeurs pNode et qNode, les deux points initiaux à la tête qNode. Ensuite, parcourez jusqu'à la fin de la liste et le pNode ne traversera que lorsqu'il y a une différence entre le nombre et la position est supérieure à 0 et les incréments de pthNode une fois dans chaque boucle.

static ListNode nthNode(int pos){
ListNode pNode=head;
ListNode qNode=head;
int count =0;
while(qNode!=null){
    count++;
    if(count - pos > 0)
        pNode=pNode.next;
    qNode=qNode.next;
}
return pNode;
}
1
répondu Rohit 2014-08-25 13:39:11
public int nthFromLast(int n){
    Node current = head;
    Node reference = head;      
    for(int i=0;i<n;i++){
        reference=reference.getNext();
    }
    while(reference != null){
        current = current.getNext();
        reference = reference.getNext();
    }
    return current.getData();
}
1
répondu kaila88 2015-04-13 23:22:48

utilisez deux pointeurs pTemp et NthNode. Au début, les deux points pointent vers le noeud de tête de la liste. NthNode commence à bouger seulement après que pTemp ait fait n mouvements. À partir des deux va de l'avant jusqu'à ce que le pTemp atteigne la fin de la liste. En conséquence, NthNode pointe vers nth node à partir de la fin de la liste lié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;
}

Consulter des Manuels scolaires : "une Structure de Données et Algorithmes Facile en Java"

1
répondu Balasubramanian 2015-05-11 13:54:05

pour comprendre ce problème, nous devrions faire une analogie simple avec un exemple de mesure. Disons que vous devez trouver l'endroit de votre bras à exactement 1 mètre de votre majeur, comment mesureriez-vous? Vous prendriez juste une règle avec une longueur de 1 mètre et mettez l'extrémité supérieure de cette règle au bout de votre majeur et l'extrémité inférieure du mètre sera exactement 1 mètre de distance du haut de votre majeur.

Ce que nous faisons dans cet exemple être le même, nous avons juste besoin d'un cadre avec n-élément large et ce que nous devons faire est de mettre le cadre à la fin de la liste, donc le noeud de départ du cadre sera exactement N-E élément à la fin de la liste.

C'est notre liste en supposant que nous avons M éléments dans la liste, et notre cadre avec n élément large;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

<-- Frame -->

Cependant, nous n'avons besoin que des limites du cadre, donc la limite finale du cadre s'éloignera exactement (N-1) des éléments démarrez la limite du cadre. Il ne faut donc stocker que ces éléments limites. Appelons-les A et B;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

A <- N-Element Wide-> B

la première chose que nous devons faire est de trouver B, qui est la fin du cadre.

ListNode<T> b = head;
int count = 1;

while(count < n && b != null) {
    b = b.next;
    count++;
}

maintenant b est l'élément n-e de la matrice, et a est situé sur la tête . Donc notre cadre est réglé, ce que nous allons faire c'est incrémenter les deux noeuds de Frontière pas à pas jusqu'à ce que b atteint à la fin de la liste où un n-th-pour-le-dernier élément;

ListNode<T> a = head;

while(b.next != null) {
    a = a.next;
    b = b.next;
}

return a;

pour rassembler tout, et avec les contrôles de tête, N < M (où M est la taille de la liste) les contrôles et autres choses, voici la méthode de solution complète;

public ListNode<T> findNthToLast(int n) {
    if(head == null) {
        return null;
    } else {
        ListNode<T> b = head;
        int count = 1;

        while(count < n && b != null) {
            b = b.next;
            count++;
        }

        if(count == n && b!=null) {
            ListNode<T> a = head;

            while(b.next != null) {
                a = a.next;
                b = b.next;
            }

            return a;
        } else {
            System.out.print("N(" + n + ") must be equal or smaller then the size of the list");
            return null;
        }
    }
}
1
répondu Levent Divilioglu 2016-03-15 21:57:06

vous pouvez également résoudre le problème ci-dessus en utilisant des tables de hachage.Les entrées de la table de hachage sont la position du noeud et l'adresse du noeud. Donc si nous voulons trouver le nième noeud à partir de la fin(cela signifie m-n+1 à partir du premier où m est le nombre de noeuds).Maintenant quand nous entrons les entrées de la table de hachage nous obtenons le nombre de noeuds.Les étapes sont: -

1.Parcourir chaque noeud et faire les entrées correspondantes dans la table de hachage.

2.Rechercher le noeud m-n+1 dans la table de hachage que nous obtenons adresse.

le Temps de la complexité est O(n).

0
répondu Shiv Shakti 2012-08-18 06:32:44

je pense qu'il y a une faille dans le code de question, et je me demande si elle a été prise d'un livre Comment est-ce possible... il peut s'exécuter correctement mais le code est quelque peu logiquement incorrect. À l'intérieur de la boucle for... la condition if doit être vérifiée par rapport à p2->next ! = NULL

 for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
       if (p2->next == null) {
       return null; // not found since list size < n
   }

...le repos est très bien et l'explication comme donné déjà les déplacements de code p2 (n-1) les positions avancent à p1 , puis en boucle pendant qu'il les déplace simultanément jusqu'à p2->next atteint la fin .. n'hésitez pas à dire si vous trouvez ma réponse incorrecte

0
répondu user1107108 2012-09-30 15:33:40

Le problème donné dans la carrière de la coupe du livre est légèrement différente. Il dit trouver la nième dernier élément d'une seule liste liée.

Voici mon code:

    public void findntolast(int index)
    {
        Node ptr = front; int count = 0;
        while(ptr!=null)
        {
            count++;
            if (count == index)
            {
                front = ptr;
                break;
            }
            ptr = ptr.next;
        }
        Node temp=front;
        while(temp!=null)
        {
            Console.WriteLine(temp.data);
            temp=temp.next;
        }
    }
0
répondu Akshay 2012-12-23 09:13:01

solution Récursive:

Node findKth (Node head, int count, int k) {
    if(head == null)
        return head;
    else {
        Node n =findKth(head.next,count,k);
        count++;

        if(count == k)
            return head;

        return n;
    }
}
0
répondu Maher Rezeq 2013-07-01 18:23:15

pouvez-vous utiliser une structure de données supplémentaire .. si c'est le cas, ce sera simple ... commencer à pousser tous les nœuds d'une pile, de maintenir un contre un pop. selon votre exemple, 8->10->5->7->2->1->5->4->10->10 commencez à lire la liste liée et commencez à pousser les noeuds ou les données de noeud->sur une pile. donc la pile ressemblera à top->{10, 10,4, 5, 1, 2, 7, 5, 10, 8}<-en bas.

maintenant commencer à sauter du haut de la pile en maintenant un compteur=1 et chaque fois que vous pop augmenter la counter par 1, lorsque vous atteignez n-th element (dans votre exemple 7ème element) stop popping.

note: Ceci imprimera ou récupérera les données / noeuds dans l'ordre inverse

0
répondu funnyCoder 2013-12-27 05:14:55

voici le code en utilisant 2 approche de pointeur: ( source )

Lent et plus Rapide pointeur approche

struct node
{
  int data;
  struct node *next;
}mynode;


mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/)
{
  mynode *ptr1,*ptr2;
  int count;

  if(!head)
  {
    return(NULL);
  }

  ptr1  = head;
  ptr2  = head;
  count = 0;

  while(count < n)
  {
     count++;
     if((ptr1=ptr1->next)==NULL)
     {
        //Length of the linked list less than n. Error.
        return(NULL);
     }
  }

  while((ptr1=ptr1->next)!=NULL)
  {
    ptr2=ptr2->next;
  }

  return(ptr2);
}



récursion

node* findNthNode (node* head, int find, int& found){
    if(!head) {
        found = 1;
        return 0;
    }
    node* retval = findNthNode(head->next, find, found);
    if(found==find)
        retval = head;
    found = found + 1;
    return retval;
}

0
répondu kinshuk4 2014-05-09 08:17:05

mon approche, ce que je pense est simple et a la complexité de temps O(N).

Étape 1: tout d'Abord à obtenir le nombre de nombre de nœuds. Exécuter une boucle pour partir du premier noeud au dernier noeud

Étape 2: Une fois que vous avez le compte, appliquez les mathématiques simples, par exemple si nous avons trouver 7ème noeud au dernier noeud et le compte de tous les noeuds est de 12, puis (count-index) - 1 donnera un peu de kème noeud, jusqu'à ce que vous aurez à traverser et il sera le nème noeud à le dernier nœud. Dans ce cas (12 -7)-1 = 4

si les éléments sont 8->10->5->7->2->1->5->4->10->10 alors le résultat est 7ème à dernier noeud est 7, ce qui n'est rien d'autre que le 4ème noeud du début.

0
répondu Dhananjaya HS 2014-12-25 22:53:15

en java je vais utiliser -

public class LL {
  Node head;
  int linksCount;

   LL(){
     head = new Node();
     linksCount = 0;
   }

  //TRAVERSE TO INDEX
  public Node getNodeAt(int index){
    Node temp= head;
    if(index > linksCount){
        System.out.println("index out of bound !");
        return null;
    }
    for(int i=0;i<index && (temp.getNext() != null);i++){
        temp = temp.getNext();
    }
    return temp.getNext();
  }
}
0
répondu Manisha 2015-06-29 21:51:39

personne ici n'a remarqué que la version de Jonathan lancera une NullPinterException si le n est plus grand que la longueur de LinkedList. Voici ma version:

public Node nth(int n){
        if(head == null || n < 1) return null;

        Node n1 = head;
        Node n2 = head;
        for(int i = 1; i < n; i++){
            if(n1.next == null) return null; 
            n1 = n1.next;
        }

        while (n1.next != null){
            n1 = n1.next;
            n2 = n2.next;
        }
        return n2;
}

je fais juste peu de changement ici: quand le noeud n1 avance, au lieu de vérifier si n1 est nul, je vérifie la météo n1.next est null, ou bien dans la boucle while n1.next lancera une NullPinterException.

0
répondu sofia 2016-04-09 03:03:06

Voici la version C# de "finding nth child" De Linklist.

public Node GetNthLast(Node head, int n)
    {
        Node current, nth;
        current = nth = head;
        int counter = 0;

        while (current.next != null)
        {
            counter++;
            if (counter % n == 0)
            {
                for (var i = 0; i < n - 1; i++)
                {
                    nth = nth.next;
                }
            }
            current = current.next;
        }
        var remainingCounts = counter % n;
        for (var i = 0; i < remainingCounts; i++)
        {
            nth = nth.next;
        }
        return nth;
    }
0
répondu Shafqat Ali 2016-08-21 22:45:29

dépendant de la tolérance de coût de mémoire (O(k) dans cette solution) nous pourrions attribuer un tableau de pointeurs de longueur k, et le peupler avec les noeuds comme un tableau circulaire tout en traversant la liste liée.

quand nous aurons fini de traverser la liste liée, le premier élément du tableau (assurez-vous de calculer correctement l'index 0 car c'est un tableau circulaire) nous aurons la réponse.

si le premier élément du tableau est nul, il n'y a pas la solution à notre problème.

0
répondu jsign 2016-11-25 02:51:24