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). Par défaut, déplacez un pointeur de n nœuds. Avancez les deux pointeurs jusqu'à ce que le pointeur avancé atteigne le point final, nul. 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;
  }
}