[JAVA] Gymnastique algorithmique 14

Swap Nth Node with Head (Easy)

La description

La tête de la liste à liaison unique et l'entier "N" sont passés en arguments. Échangez la tête et le Nième nœud de la tête. La valeur de retour est la tête de la nouvelle liste Linked.

Exemple

Regardons un exemple avec N = 4. Puisque la tête est le premier et que 28 du quatrième nœud et 7 de la tête sont échangés, cela devient comme suit.

Solution Runtime Complexity O(n) Il prend au pire O (n) car il doit scanner la liste liée. Space Complexity O(1) Étant donné que seuls plusieurs pointeurs sont utilisés, l'efficacité de la mémoire est O (1).

Step By Step Préparez deux pointeurs. Boucle jusqu'à ce que le pointeur actuel pointe vers le Nième nœud. Le pointeur actuel pointe vers le 4ème nœud, arrêtez donc la boucle ici. De là, nous échangerons des nœuds. Maintenant que nous avons permuté, nous retournerons un pointeur vers le courant.

la mise en oeuvre

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

Impressions

Si vous souhaitez appliquer des opérations simples telles que Permuter et trier à la liste liée Je pense que vous pouvez trouver une solution en utilisant plusieurs pointeurs.