Algorithmusgymnastik 14

Swap Nth Node with Head (Easy)

Erläuterung

Der Kopf der einfach verknüpften Liste und die Ganzzahl "N" werden als Argumente übergeben. Tauschen Sie den Kopf und den N-ten Knoten vom Kopf aus. Der Rückgabewert ist der Kopf der neuen verknüpften Liste.

Beispiel

Schauen wir uns ein Beispiel mit N = 4 an. Da Kopf der erste ist und 28 des vierten Knotens und 7 des Kopfes ausgetauscht werden, wird es wie folgt.

Solution Runtime Complexity O(n) Im schlimmsten Fall dauert es O (n), da es gegen die verknüpfte Liste scannen muss. Space Complexity O(1) Da nur mehrere Zeiger verwendet werden, beträgt die Speichereffizienz O (1).

Step By Step Bereiten Sie zwei Zeiger vor. Schleife, bis der aktuelle Zeiger auf den N-ten Knoten zeigt. Der aktuelle Zeiger zeigt auf den 4. Knoten. Stoppen Sie die Schleife hier. Von hier aus werden wir Knoten austauschen. Nachdem wir getauscht haben, geben wir einen Zeiger auf den aktuellen Wert zurück.

Implementierung

SwapNth.java

class SwapNth{
  // Node indices starts from 1.
  public LinkedListNode SwapNthNode(LinkedListNode head, int n) {

    if (head == null || n < 1) return head; // Edge case

    LinkedListNode cur = head;
    LinkedListNode prev = null;

    int count = 1;

    while (count < n && cur != null) {
      prev = cur;
      cur = cur.next;
      count++;
    }

    if (cur == null) return head;

    // Swapping
    prev.next = head;
    LinkedListNode temp = head.next;
    head.next = cur.next;
    cur.next = temp;
    
    return cur;
  }
} 

Impressionen

Wenn Sie einfache Vorgänge wie Auslagern und Sortieren auf die verknüpfte Liste anwenden möchten Ich denke, Sie können eine Lösung finden, indem Sie mehrere Zeiger verwenden.