Algorithmus Gymnastik 18

Reverse k Elements Eine einzelne Linkliste und die Ganzzahl "k" werden als Argumente übergeben. Eine algorithmische Übung, die k Elemente einer Liste invertiert. Wenn k <= 1 ist, bleibt die Liste unverändert. Wenn k> = n (n ist die Länge der Linkliste), kehren Sie die gesamte Linkliste um.

Beispiel

Das Folgende ist ein Beispiel für die Inversion für jeweils 3 Elemente mit k = 3. Das Folgende ist ein Beispiel für die Inversion für jeweils 4 Elemente mit k = 4.

Solution Es ist eine relativ einfache Angelegenheit, aber der Code selbst ist etwas kompliziert, da er mit wenigen Zeigern verfolgt werden muss. In diesem Algorithmus geht es darum, "zwei invertierte Listen zu verwenden". Die erste ist eine vollständig invertierte Liste, die schließlich als Rückgabewert zurückgegeben wird. Die zweite ist eine partielle (k Element) Inversionsliste, die mit der gesamten Inversionsliste verbunden ist.

1. umgekehrt: Ein Zeiger auf den Anfang der gesamten invertierten Liste. Dies ist der Rückgabewert.
2. current_head: Der Beginn einer teilweise invertierten Liste der Größe "k".
3. current_tail: Das Ende der teilweise invertierten Liste von size'k '.
4. prev_tail: Das Ende der vollständig invertierten Liste, die bereits verarbeitet wurde.

Angenommen, Sie haben k = 5 und die folgende Liste:

Es fühlt sich an, als würde man für jedes k-Element eine partielle Inversionsliste erstellen und diese mit der vollständigen Inversionsliste verbinden.

Implementierung

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