[JAVA] Gymnastique algorithmique 17

Rotate a Linked List

La description

Un exercice algorithmique qui fait pivoter la liste de liens n fois en spécifiant le nœud principal de la liste de liens unique et l'entier n.

Voici deux exemples. La liste de liens passée en argument et la sortie après l'entier n = 2 rotations.

Notez que la valeur de n peut être supérieure à la longueur de la liste de liens. Screen Shot 2020-01-22 at 5.20.32.png

Lorsque n = -2, Screen Shot 2020-01-22 at 5.20.53.png

Solution Runtime Complexity O(n) n est la longueur de la liste de liens. Memory Complexity O(1) Il n'est pas nécessaire d'utiliser une nouvelle structure de données. Pointeur uniquement.

  1. Tout d'abord, recherchez la longueur de la liste de liens.
  2. Si n est négatif ou si n est supérieur à la longueur de la liste de liens, ajustez le nombre de tours requis à la fin de la liste de liens. Le nombre ajusté est toujours l'entier N (0 <= N <n). Si la vitesse de rotation ajustée est 0, il renvoie simplement le pointeur de tête. Cela signifie qu'aucune rotation n'était nécessaire.
  3. Trouvez le nième nœud "x" du dernier nœud de la liste de liens. Il atteint essentiellement le nœud x avec une longueur de "n-N". Le pointeur suivant vers le nœud avant ce nœud sera le dernier nœud de la liste et doit être mis à jour pour pointer vers NULL.
  4. À partir de x, accédez au dernier nœud de la liste de liens. Force le nœud principal à mettre à jour le pointeur suivant sur le dernier nœud.
  5. Créez new_head comme nouveau nœud principal. new_head sera en haut de la liste de liens après avoir effectué n rotations.

Puisque "une image vaut mille mots", faisons tourner la liste de liens ci-dessus avec n = 2 en utilisant l'algorithme ci-dessus. Screen Shot 2020-01-22 at 5.37.14.png Screen Shot 2020-01-22 at 5.37.29.png Screen Shot 2020-01-22 at 5.37.44.png Screen Shot 2020-01-22 at 5.37.57.png Screen Shot 2020-01-22 at 5.38.11.png Screen Shot 2020-01-22 at 5.38.23.png

la mise en oeuvre

RotateList.java


class RotateList{

  private int getListSize(LinkedListNode head) {
    LinkedListNode curr = head;
    int listSize = 0;

    while (curr != null) {
       listSize++;
       curr = curr.next;
     }
     return listSize;
  }

  private int adjustRotatationsNeeded(int n, int length) {
    return n < 0 ? length - (n * -1) % length : n % length;
  }

   public LinkedListNode rotate_list(LinkedListNode head, int n) {
     
     int listSize = 0;
     listSize = getListSize(head);

     n = adjustRotatationsNeeded(n, listSize);

     if (n == 0) {
       return head;
     }

    // Find the startNode of rotated list.
    // If we have 1,2,3,4,5 where n = 2,
    // 4 is the start of rotated list

     LinkedListNode temp = head;
     int rotationsCount = listSize - n - 1;
     while(rotationsCount > 0) {
       temp = temp.next;
       rotationsCount--;
     }

     LinkedListNode new_head = temp.next;
     temp.next = null;

     LinkedListNode tail = new_head;
     while (tail.next != null) {
       tail = tail.next;
     }

     tail.next = head;
     head = new_head;
     
    return new_head;
  }
}

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes