[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. Screen Shot 2020-01-10 at 16.35.08.png 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. Screen Shot 2020-01-10 at 16.35.25.png

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. Screen Shot 2020-01-10 at 16.42.22.png Boucle jusqu'à ce que le pointeur actuel pointe vers le Nième nœud. Screen Shot 2020-01-10 at 16.43.15.png Le pointeur actuel pointe vers le 4ème nœud, arrêtez donc la boucle ici. Screen Shot 2020-01-10 at 16.45.12.png De là, nous échangerons des nœuds. Screen Shot 2020-01-10 at 16.46.28.png Screen Shot 2020-01-10 at 16.47.12.png Screen Shot 2020-01-10 at 16.47.32.png Screen Shot 2020-01-10 at 16.47.50.png 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.

Recommended Posts

Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes