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. Voici un exemple d'inversion pour 4 éléments avec k = 4.

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:

Cela ressemble à créer une liste d'inversion partielle pour chaque élément k et à la connecter à la liste d'inversion complète.

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