Deux pointeurs : lent et rapide

Le modèle des pointeurs lent-rapide, également appelé modèle de la tortue et du lièvre, utilise deux pointeurs qui se déplacent à des vitesses différentes dans la même séquence. Contrairement aux pointeurs placés aux extrémités opposées, ils commencent tous les deux au début. Le pointeur lent avance d’une étape à la fois ; le pointeur rapide en avance de deux, voire davantage. Leur différence de vitesse crée des invariants utiles : le pointeur lent suit un « préfixe valide », tandis que le pointeur rapide parcourt les éléments suivants à la recherche de certaines conditions.

Dans un tableau trié, les doublons sont adjacents. Le pointeur lent suit la dernière valeur unique écrite ; le pointeur rapide parcourt les éléments suivants. Lorsque le pointeur rapide atteint une valeur différente de nums[slow], avancez le pointeur lent et copiez la nouvelle valeur. Cet algorithme en place s’exécute en O(n) avec un espace supplémentaire de O(1) : c’est une question d’entretien classique qui vérifie votre maîtrise du modèle des pointeurs de lecture-écriture.

Déplacez tous les zéros à la fin tout en préservant l’ordre relatif des éléments non nuls. Le pointeur lent indique la prochaine position destinée à un élément non nul. Le pointeur rapide recherche les valeurs non nulles. Lorsque le pointeur rapide en trouve une, copiez-la à la position du pointeur lent, puis avancez les deux pointeurs. Après le parcours, remplissez de zéros les positions allant du pointeur lent à la fin. Complexité : O(n) en temps et O(1) en espace.

L’étape de partition du tri rapide réorganise les éléments en place afin que toutes les valeurs < au pivot précèdent les valeurs >= au pivot. Le schéma de Lomuto utilise un pointeur lent, qui indique la dernière position d’un petit élément, et un pointeur rapide, qui parcourt le tableau vers l’avant. Lorsque le pointeur rapide trouve un petit élément, incrémentez le pointeur lent et échangez les deux éléments. Cette opération s’exécute en O(n) avec un espace supplémentaire de O(1).

Avec des pointeurs lent-rapide sur une liste chaînée, le pointeur rapide avance de deux nœuds par étape et le pointeur lent d’un seul. Lorsque le pointeur rapide atteint la fin, le pointeur lent se trouve au milieu. Cette approche en un seul parcours, en O(n), est bien plus simple que de compter les nœuds puis de parcourir la moitié de la liste. Elle est utilisée comme sous-étape du tri fusion de listes chaînées et de la détection de palindromes dans les listes chaînées.

La détection de cycle de Floyd place les pointeurs lent et rapide au début d’une liste chaînée. Le pointeur lent avance d’un nœud ; le pointeur rapide de deux. Si un cycle existe, le pointeur rapide finira par rattraper le pointeur lent et ils se rencontreront à l’intérieur du cycle. Si fast atteint None, il n’y a pas de cycle. La rencontre est garantie, car fast gagne une étape sur slow à chaque itération : dans un cycle de longueur k, ils se rencontrent au plus k étapes après l’entrée de slow dans le cycle.

Après avoir détecté un cycle (slow == fast), replacez l’un des pointeurs au début. Avancez maintenant les deux pointeurs d’une étape à la fois. Ils se rencontreront au point d’entrée du cycle. Cette méthode utilise la propriété mathématique selon laquelle la distance entre le début et l’entrée du cycle est égale à la distance entre le point de rencontre et l’entrée du cycle, modulo la longueur du cycle. C’est un résultat mathématique élégant qui apparaît fréquemment dans les problèmes d’entretien difficiles.

Les pointeurs lent-rapide s’appliquent au-delà des listes chaînées, à tout processus cyclique. Un « nombre heureux » parcourt un cycle de sommes des carrés de ses chiffres ; si n n’est pas heureux, la séquence finit par boucler. Détectez la boucle avec slow, qui avance d’une étape correspondant à un carré de chiffre, et fast, qui avance de deux étapes. S’ils se rencontrent en 1, n est heureux ; sinon, il est piégé dans un cycle qui ne contient pas 1. Il s’agit de l’algorithme de Floyd appliqué à une liste chaînée virtuelle de valeurs.

Trouvez le nième nœud depuis la fin d’une liste chaînée en un seul parcours, à l’aide de deux pointeurs. Avancez le pointeur rapide de n étapes. Avancez ensuite les deux pointeurs ensemble jusqu’à ce que le pointeur rapide atteigne la fin : le pointeur lent se trouve alors au nième nœud depuis la fin. Pour supprimer ce nœud, conservez un pointeur prev juste derrière le pointeur lent. Il s’agit d’un problème classique sur les listes chaînées en un seul parcours, qui évite de compter d’abord la longueur totale.

Le raisonnement lent-rapide s’applique également aux problèmes sur les tableaux et les chaînes. Lors de la compression d’une chaîne codée par longueurs de séquences, le pointeur lent indique la position d’écriture et le pointeur rapide parcourt les éléments jusqu’à la fin de chaque séquence. Lorsque tous les caractères de la séquence sont égaux au caractère suivi par slow, avancez fast ; sinon, enregistrez la séquence et mettez à jour slow. Cette méthode s’exécute en O(n) en un seul parcours, avec un espace de O(1).

Utilisez des pointeurs aux extrémités opposées lorsque le problème porte sur des paires dont la somme atteint une cible, sur des vérifications de palindrome ou sur la réduction d’une fenêtre par les deux côtés. Utilisez des pointeurs lent-rapide lorsque vous avez besoin d’un pointeur d’écriture, pour supprimer ou déplacer des éléments, lorsque vous traitez la structure d’une liste chaînée, par exemple pour trouver son milieu ou un cycle, ou lorsque vous détectez des cycles dans une séquence de valeurs. Les deux modèles éliminent les boucles imbriquées et atteignent O(n) ; le facteur déterminant est la structure du parcours.

Testez votre compréhension des concepts de Structures de données & algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris que le modèle lent-rapide, ou lecture-écriture, maintient un pointeur d’écriture sur la prochaine position valide tandis qu’un pointeur rapide parcourt les éléments vers l’avant : c’est le fondement de la suppression, de la déduplication et du déplacement des zéros en place, que la tortue et le lièvre de Floyd détectent les cycles en O(n) avec un espace de O(1) en exploitant la différence de vitesse entre deux pointeurs, et qu’après la détection d’un cycle, replacer un pointeur au début puis avancer les deux pointeurs à la même vitesse permet de trouver l’entrée du cycle grâce à une égalité démontrable des distances. Nous allons maintenant étudier l’API des chaînes Python pour les entretiens.