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.

Lorsque n = -2,

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.

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