Algorithmus Gymnastik 17

Rotate a Linked List

Erläuterung

Eine algorithmische Übung, bei der die Verknüpfungsliste n-mal gedreht wird, indem der Kopfknoten der einzelnen Verknüpfungsliste und die Ganzzahl n angegeben werden.

Unten sind zwei Beispiele. Die als Argument übergebene Verknüpfungsliste und die Ausgabe nach der Ganzzahl n = 2 Umdrehungen.

Beachten Sie, dass der Wert von n größer sein kann als die Länge der Linkliste.

Wenn n = -2,

Solution Runtime Complexity O(n) n ist die Länge der Linkliste. Memory Complexity O(1) Es ist nicht erforderlich, eine neue Datenstruktur zu verwenden. Nur Zeiger.

1. Ermitteln Sie zunächst die Länge der Linkliste.
2. Wenn n negativ ist oder wenn n größer als die Länge der Linkliste ist, stellen Sie die erforderliche Anzahl von Umdrehungen am Ende der Linkliste ein. Die angepasste Zahl ist immer die ganze Zahl N (0 <= N <n). Wenn die eingestellte Drehzahl 0 ist, wird nur der Kopfzeiger zurückgegeben. Dies bedeutet, dass keine Drehung erforderlich war.
3. Suchen Sie den nth'x'-Knoten vom letzten Knoten in der Linkliste. Es erreicht im Grunde den Knoten x mit einer Länge von "n-N". Der nächste Zeiger auf den Knoten vor diesem Knoten ist der letzte Knoten in der Liste und sollte so aktualisiert werden, dass er auf NULL zeigt.
4. Wechseln Sie von x zum letzten Knoten in der Linkliste. Bewirkt, dass der Kopfknoten den nächsten Zeiger auf dem letzten Knoten aktualisiert.
5. Erstellen Sie new_head als neuen Kopfknoten. new_head steht nach n Umdrehungen ganz oben in der Linkliste.

Da "ein Bild mehr sagt als tausend Worte", drehen wir die obige Linkliste mit n = 2 unter Verwendung des obigen Algorithmus.

Implementierung

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