[JAVA] Gymnastique algorithmique 18

Reverse k Elements Une seule liste de liens et l'entier "k" sont passés comme arguments. Un exercice algorithmique qui inverse k éléments d'une liste. Si k <= 1, la liste reste inchangée. Si k> = n (n est la longueur de la liste de liens), inversez toute la liste de liens.

Exemple

Voici un exemple d'inversion pour 3 éléments avec k = 3. Screen Shot 2020-01-23 at 9.51.00.png Voici un exemple d'inversion pour 4 éléments avec k = 4. Screen Shot 2020-01-23 at 9.51.40.png

Solution C'est une question relativement simple, mais le code lui-même est un peu compliqué car il doit être suivi avec quelques pointeurs. Le but de cet algorithme est "d'utiliser deux listes inversées". Le premier est une liste totalement inversée qui est finalement retournée comme valeur de retour. La seconde est une liste d'inversion partielle (k éléments) qui se connecte à toute la liste d'inversion.

  1. inversé: un pointeur vers le début de toute la liste inversée. Ce sera la valeur de retour.
  2. current_head: Le début d'une liste partiellement inversée de taille "k".
  3. current_tail: La fin de la liste partiellement inversée de size'k '.
  4. prev_tail: La fin de la liste entièrement inversée qui a déjà été traitée.

Par exemple, supposons que vous ayez k = 5 et que vous ayez la liste suivante: Screen Shot 2020-01-23 at 10.01.14.png

Cela ressemble à créer une liste d'inversion partielle pour chaque élément k et à la connecter à la liste d'inversion complète. Screen Shot 2020-01-23 at 10.02.12.png Screen Shot 2020-01-23 at 10.06.26.png

la mise en oeuvre

ReverseK.java


class ReverseK{
  LinkedListNode reverse_k_nodes(LinkedListNode head, int k) {
    
    if (k <= 1 || head == null) {
      return head;
    }

    LinkedListNode reversed = null;
    LinkedListNode prev_tail = null;

    while (head != null & k > 0) {

      LinkedListNode current_head = null;
      LinkedListNode current_tail = head;

      int n = k;

      while (head != null && n > 0) {
        LinkedListNode temp = head.next;
        head.next = current_head;
        current_head = head;
        head = temp;
        n--;
      }

      if (reversed == null) {
        reversed = current_head;
      }

      if (prev_tail != null) {
        prev_tail.next = current_head;
      }
      prev_tail = current_tail;
    }

    return reversed;
  }
}

Recommended Posts

Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
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
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
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é
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes