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

Question

La fonction suivante est d'essayer de trouver de l' nth pour le dernier élément d'une seule liste liée.

Par exemple:

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

Quelqu'un peut-il m'aider sur la façon dont ce code fonctionne ou est-il mieux et plus simple d'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;
 }

Answer 1

La clé de cet algorithme est de définir deux pointeurs p1 et p2 part en n-1 des nœuds au départ, nous voulons p2 de point à l' (n-1)th nœud à partir du début de la liste, puis nous passons p2 jusqu'à ce qu'il atteigne l' last le nœud de la liste. Une fois p2 atteint à la fin de la liste p1 sera pointant vers le n-ième nœud à partir de la fin de la liste.

J'ai mis l'explication en ligne, comme des commentaires. Espérons que cela 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;
 }

Sinon, nous pouvons définir p1 et p2 part par n nœuds au lieu de (n-1) puis de déplacer p2 jusqu'à la fin de la liste au lieu de les déplacer jusqu'au dernier nœud:

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;

Answer 2

Cela ressemble à un problème.

Dans tous les cas, votre algorithme fonctionne en créant d'abord des références à deux nœuds dans votre liste chaînée qui sont N noeuds en dehors. Ainsi, dans votre exemple, si N est de 7, puis il sera mis en p1 à 8 et p2 à 4.

Il passera ensuite à chaque nœud de référence au nœud suivant dans la liste jusqu'à p2 atteint le dernier élément dans la liste. Encore une fois, dans votre exemple, ce sera quand p1 est de 5 et p2 est de 10. À ce stade, p1 est en se référant à la Nième le dernier élément dans la liste (par la propriété qu'ils sont N noeuds en dehors).

Answer 3

Que pensez-vous au sujet de cette approche.

1. Le comte de la longueur de la linkedlist.
2. Nœud réel indice de la tête = linkedlist longueur - index donné;
3. Écrire une fonction pour travesre de la tête et obtenir le nœud à l'index ci-dessus.

Answer 4

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

Answer 5

Depuis cela sonne comme 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 certains petit échantillon de données. Utilisez votre débogueur pour exécuter les lignes de l'étape-par-étape (vous pouvez définir un point d'arrêt au début de la fonction). Cela devrait vous donner une idée de comment le code fonctionne.

Vous pouvez également Console.WriteLine() à la sortie des variables d'intérêt.