[JAVA] Exercices d'algorithme 13

Nth from the Last Node (Easy)

La description

Puisque le nœud principal de la liste à liaison unique et l'entier n sont passés, Implémentons un algorithme qui renvoie ** le nième nœud à partir de la fin (renvoie null si n est hors de portée)

Solution L'idée est d'utiliser deux pointeurs séparés par n nœuds. Définissez d'abord le premier pointeur pour qu'il pointe vers la tête et le second pour pointer vers le nième nœud (paramètre par défaut). Si le deuxième nœud atteint le point final de la liste, null, lors de l'initialisation, il retourne null (hors limites). Déplacez ensuite les deux pointeurs vers l'avant jusqu'à ce que le deuxième pointeur atteigne le point final de la boucle. Une fois la boucle terminée, le premier pointeur pointera vers le nième nœud à partir de la fin, de sorte que le pointeur sera renvoyé. Runtime Complexity O(n) Le temps d'exécution est O (n) car il scanne linéairement par rapport à la liste liée Singley. Space Complexity O(1) Puisque deux pointeurs sont utilisés, l'efficacité de la mémoire est une constante de O (1).

Exemple

Regardons un exemple dans la liste ci-dessous qui recherche le troisième et dernier nœud (n = 3). Screen Shot 2020-01-09 at 19.07.12.png Par défaut, déplacez un pointeur de n nœuds. Screen Shot 2020-01-09 at 19.08.10.png Avancez les deux pointeurs jusqu'à ce que le pointeur avancé atteigne le point final, nul. Screen Shot 2020-01-09 at 19.12.02.png Screen Shot 2020-01-09 at 19.12.22.png Screen Shot 2020-01-09 at 19.12.49.png Vous avez maintenant trouvé l'avant-dernier nœud.

la mise en oeuvre

lastNthFromList.java


class lastNthFromList{
  public LinkedListNode FindNthFromLast(LinkedListNode head,int n) {
    
    if (head == null || n < 1) return null; // edge case

    LinkedListNode targetNode = head;
    LinkedListNode searchNode = head;

    while (searchNode != null && n != 0) {
      searchNode = searchNode.next;
      n--;
    }

    if (n != 0) return null; // check out-of-bounds
    
    while(searchNode != null) {
      targetNode = targetNode.next;
      searchNode = searchNode.next;
    }

    return targetNode;
  }
}

Recommended Posts

Exercices d'algorithme 13
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Exercice d'algorithme 6
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 15
Algorithme Python
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Mémorandum Python (algorithme)
Exercice Pandas (édition)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes