- Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. Cette sheet ne le redémontre pas : elle l'instancie trois fois, une par habit.
- Invariant = conteneur + tranche + « exactement ». c00, pas 2. Ici le conteneur n'est pas un accumulateur mais une liste, et il y en a deux à décrire, pas une : c'est tout l'enjeu du pas 3.
- Variant = entier ≥ 0 strictement décroissant. c00, pas 3. Celui de l'inversion n'est pas un indice — il n'y en a pas — mais la longueur du suffixe non encore traité.
- Complexité composée. c00, pas 5. Ici le second facteur est trivial (O(1) par tour) ; ce qui se discute est l'espace, et c'est là que Floyd se justifie (pas 5).
- Un nœud est une identité, pas une valeur. Deux nœuds peuvent porter le même entier. Comparer avec
is, jamais==— la détection de cycle du pas 5 en dépend entièrement.
next, pas de prev. On reçoit head, et rien d'autre — ni longueur, ni queue, ni accès par indice. Une liste doublement chaînée rend l'inversion triviale et n'est pas le sujet.
H2L'espace exigé est O(1). Sans cette contrainte, tout tombe : copier les valeurs dans une liste Python résout l'inversion, le milieu et le cycle en trois lignes. C'est cette hypothèse, et elle seule, qui rend les trois habits nécessaires.
H3Les nœuds sont distincts en identité ; leurs valeurs peuvent se répéter. Tout test de rencontre se fait sur l'objet (is).
H4« En place » signifie qu'on réattribue des next et qu'on n'alloue aucun nœud — sauf la sentinelle du pas 6, qui est un unique nœud, donc O(1).
H5On énonce le squelette et les phrases. Le corps se remplit devant l'interlocuteur : une sheet de coding ne contient jamais la solution complète.
La chaîne
Le signal, et le contre-signal tronc
Une structure à accès séquentiel — pas d'indice, pas de longueur connue — et une opération demandée « au milieu », « à l'envers » ou « y a-t-il un cycle », en place, en O(1) mémoire.
Le contre-signal est net : de l'accès aléatoire fréquent. a[i] coûte O(1) sur un tableau et O(i) sur une liste — trier, dichotomiser ou glisser une fenêtre sur une liste chaînée, c'est se punir pour rien.
« Je n'ai ni indice ni longueur, donc la seule information gratuite est la position de mes pointeurs, donc j'en pose deux à des vitesses différentes, ou trois à la file, donc trois habits et pas un de plus. »
Lent / rapide. Deux pointeurs, l'un avance de 1, l'autre de 2. Trois lectures d'une même idée : le milieu (quand rapide tombe, lent y est), le k-ième depuis la fin (un décalage de k, pas une vitesse), la détection de cycle (Floyd).
Inversion en place. Trois pointeurs prev, cur, nxt ; on retourne une flèche à la fois, jamais deux.
Tête factice. Un nœud sentinelle avant la tête, pour que « supprimer la tête » et « insérer avant la tête » cessent d'être des cas spéciaux.
Le fil rouge. 1 → 2 → 3 → 4 pour l'inversion ; 1 → 2 → 3 → 4 → 5 → 6 pour le milieu, puis la même liste refermée par 6 → 3 pour le cycle. Trois énoncés, deux listes, un seul jeu de flèches à suivre des yeux.
Le pattern : sauver avant de casser tronc
L'inversion tient en trois pointeurs et quatre lignes. L'ordre des deux premières n'est pas négociable : cur.next est l'unique chemin vers le reste de la liste, et l'affectation suivante l'écrase.
nxt = cur.next puis cur.next = prev · jamais l'inverseUne flèche retournée par tour, et une seule. Le tour ne touche ni prev ni le suffixe : il déplace exactement un nœud d'un côté à l'autre de la frontière.
« cur.next est mon seul chemin vers le suffixe, donc je le copie dans nxt avant de l'écraser, donc je peux retourner la flèche sans perdre la suite, donc un tour déplace exactement un nœud du suffixe vers le préfixe inversé. »
Cinq lignes, et pas une de plus. Il n'y a pas de cas particulier pour la liste vide : head = None ⇒ la boucle ne tourne pas ⇒ on renvoie None, qui est la bonne réponse. Ni pour la liste à un nœud : un tour, 1 → ∅.
Le retour est prev. À la sortie, head pointe sur l'ancienne tête, devenue la queue. Renvoyer head renvoie donc une liste d'un seul nœud : [1] au lieu de [4, 3, 2, 1]. Aucune erreur levée (pas 7).
Vérifié à l'exécution. Ce squelette confronté à vals[::-1] sur 200 000 listes aléatoires (longueurs 0 à 8, valeurs répétées comprises) : 0 désaccord.
L'invariant : deux tranches, et il faut dire les deux tronc
À l'entrée de chaque tour, la liste coupée en cur a deux moitiés, et l'invariant en décrit une chacune. Ne dire que la première est l'erreur classique : elle ne suffit pas à conclure.
prev = inversion exacte du préfixe [tête, cur) · cur = suffixe [cur, fin) intactInitialisation : prev = ∅ inverse le préfixe vide, cur = head est la liste entière — vrai gratuitement. Préservation : le tour retire un nœud en tête du suffixe et l'empile en tête de prev, donc les deux moitiés restent exactes.
« prev porte l'inversion exacte du préfixe et cur le suffixe intact, donc un tour transfère la tête du suffixe au sommet du préfixe, donc les deux moitiés restent exactes, donc quand le suffixe est vide prev est l'inversion de toute la liste. »
1 → 2 → 3 → 4. À chaque entrée de boucle, (prev, cur) et les deux tranches :
| tour | prev — préfixe inversé | cur — suffixe intact |
|---|---|---|
| entrée 1 | ∅ | 1 → 2 → 3 → 4 |
| entrée 2 | 1 → ∅ | 2 → 3 → 4 |
| entrée 3 | 2 → 1 → ∅ | 3 → 4 |
| entrée 4 | 3 → 2 → 1 → ∅ | 4 |
| sortie | 4 → 3 → 2 → 1 → ∅ | ∅ |
La conclusion s'instancie. cur = ∅ ⇒ le suffixe est vide ⇒ le préfixe [tête, ∅) est toute la liste, donc prev en est l'inversion. On conclut sur la seconde tranche : c'est elle qui, en devenant vide, fait tout le travail.
Ce qu'il ne faut pas dire. « prev contient le début inversé » — c'est vrai et ça ne conclut rien : sans « et cur est le reste, intact », rien n'interdit qu'un nœud ait été perdu en route. C'est exactement ce qui arrive au pas 7.
1 → 2 → 3 → 4arr = [1, 2, 3, 4], indices en petit sous chaque valeur. Les cases ambrées sont le préfixe déjà inversé (la liste que porte prev), le cadre vert le suffixe encore intact (la liste que porte cur) — les deux tranches de l'invariant, et rien entre elles : la frontière est exactement cur. Fais « pas › » et regarde le transfert : une case passe du vert à l'ambre par tour, jamais deux, et les deux zones restent complémentaires. La ligne du bas réécrit l'invariant à chaque image, avec ses deux moitiés ; dis-le avant de le lire. Au dernier pas le vert est vide : c'est la conclusion.
Le variant, et pourquoi l'espace est O(1)
Le variant est la longueur du suffixe depuis cur : entier, ≥ 0, et il perd exactement 1 par tour puisque le tour déplace un nœud. Terminaison en n tours, sans jamais avoir compté les nœuds.
cur, fin)| · ← variant − 1 par tour ⇒ n tours, O(n) temps, O(1) espaceL'espace ne se devine pas non plus : trois noms de variables, quel que soit n. Aucun nœud n'est alloué, aucune liste Python n'est construite — c'est la différence, et la seule, avec la solution « je copie les valeurs et je renvoie vals[::-1] ».
« Le suffixe perd un nœud par tour et sa longueur est un entier positif, donc la boucle fait exactement n tours, donc O(n) en temps, et comme je ne garde que trois pointeurs, donc O(1) en espace. »
Sur le fil rouge (n = 4) : le variant vaut 4, 3, 2, 1, 0 aux cinq entrées de boucle — 4 tours, 4 écritures de next, 0 nœud créé. Le tableau du pas 3 est exactement cette suite, lue dans la colonne de droite.
Le coût d'un tour est O(1) : une lecture, une écriture, deux réaffectations de noms. Donc O(n) — la complexité composée du prérequis, avec un second facteur trivial.
| solution | temps | espace |
|---|---|---|
| trois pointeurs, en place | O(n) | O(1) — 3 noms |
copier les valeurs, renvoyer vals[::-1] | O(n) | O(n) |
| récursion sur la queue | O(n) | O(n) — la pile d'appels |
La récursion n'est pas gratuite. Elle a l'air « sans variable auxiliaire », mais chaque appel garde un cadre : O(n) d'espace, et RecursionError au-delà de la limite CPython. Dire « O(1) » d'une inversion récursive est faux, et c'est une question d'entretien.
Lent / rapide : une vitesse double, trois lectures tronc
Un seul invariant arithmétique : rapide a parcouru exactement le double de lent. Il se lit trois fois. Milieu : quand rapide tombe au bout, lent est à la moitié. k-ième depuis la fin : là, pas de vitesse double mais un décalage constant de k. Cycle : si la liste boucle, rapide rattrape lent.
Le cycle en découle : une fois les deux pointeurs dedans, l'écart gagne 1 par tour, donc il parcourt tous les résidus modulo L et atteint 0 en moins de L tours. Sans cycle, rapide atteint ∅. Jamais de « ils pourraient se croiser sans se toucher » : l'écart change de 1, pas de 2.
« Rapide avance de deux quand lent avance d'un, donc dans un cycle l'écart gagne 1 par tour modulo la longueur, donc il atteint 0, donc ils se rencontrent — et sans cycle rapide tombe sur ∅. »
Milieu de 1 → … → 6. while fast and fast.next : (lent, rapide) = (0, 0) → (1, 2) → (2, 4) → (3, ∅). Lent s'arrête à l'indice 3, valeur 4 — le second des deux milieux d'une liste paire. Vérifié pour n = 1…199 contre n // 2 + 1 : 0 désaccord. La variante while fast.next and fast.next.next donne le premier milieu, valeur 3 : deux boucles différentes, savoir laquelle on écrit.
k-ième depuis la fin. On avance rapide de k pas, puis les deux ensemble jusqu'à rapide = ∅ : lent atterrit à l'indice n − k. Sur 1 → … → 6 : k = 2 → 5, k = 1 → 6. Ce n'est pas une vitesse double — c'est un écart figé.
Cycle 6 → 3, la même liste refermée. Cycle de longueur L = 4 (nœuds 3, 4, 5, 6). (lent, rapide) par indice : (0, 0) → (1, 2) → (2, 4) → (3, 2) → (4, 4). Rencontre au 4e tour, sur le nœud de valeur 5. Les écarts, une fois lent entré dans le cycle : 2, 3, 0 — +1 par tour modulo 4, exactement.
Contre le set de vus. Les deux sont O(n) en temps et donnent le même verdict — 0 désaccord sur 200 000 listes tirées au hasard (longueurs 0 à 8, cycle à pile ou face, point d'attache uniforme). L'écart est en mémoire : la table d'un set de 106 entrées pèse 33 554 648 octets, soit 32 Mo, contre 16 octets pour deux pointeurs. C'est la phrase à dire quand on propose le set.
6 → 3 : la rencontreDeux rubans, la même paire de pointeurs. En A (liste ouverte), le cadre vert s’arrête sur lent, l’ambre sur rapide — et c’est la ligne du bas qu’il faut lire, celle qui compte les pas franchis : 1 contre 2, puis 2 contre 4, puis 3 contre 6. Rapide en fait exactement le double, et c’est tout l’invariant. À la dernière image il est sorti du ruban — l’ambre s’arrête donc au bord — et lent est sur l’indice 3, valeur 4, le second des deux milieux de 6. En B, la liste est la même mais 6 repointe sur 3 : le cadre vert n’est plus un chemin, c’est le cycle lui-même — les quatre nœuds 3, 4, 5, 6 — et rapide recule sur le ruban quand il boucle. Regarde la ligne du bas image par image : tant que lent est dehors, l’écart ne veut rien dire ; dès qu’il entre (image 3) l’écart vaut 2, puis 3, puis 0 — il gagne 1 par tour modulo 4, donc il ne peut pas sauter par-dessus 0. Rencontre à l’image 5, sur le nœud 5.
La tête factice : supprimer la tête cesse d'être un cas
Toute modification d'une liste chaînée s'écrit depuis le nœud précédent — et la tête n'en a pas. D'où deux codes parallèles, l'un pour la tête, l'autre pour le reste. La sentinelle supprime la dissymétrie : un nœud jetable avant la tête, et tout nœud en a un devant lui.
dummy = Node(); dummy.next = head … retour dummy.nextOn renvoie dummy.next, jamais head : si la tête a été supprimée, head désigne un nœud qui n'est plus dans la liste. Coût : un nœud, donc O(1) — H4 tient.
« Une suppression s'écrit depuis le précédent et la tête n'en a pas, donc je lui en fabrique un, donc la boucle n'a plus qu'un seul cas, donc je renvoie dummy.next et la tête supprimée disparaît toute seule. »
3 → 1 → 3 → 4 → 3Avec la sentinelle. p = dummy ; tant que p.next : si p.next.v == 3 alors p.next = p.next.next, sinon p = p.next. Résultat : [1, 4]. La tête et la queue sont traitées par la même ligne.
Sans sentinelle, la boucle naïve. Partir de p = head et boucler sur p.next : on renvoie [3, 1, 4] — la tête survit, silencieusement. Pire sur 3 → 3 → 3 : la bonne réponse est la liste vide, la naïve renvoie [3].
Vérifié à l'exécution. La version sentinelle confrontée à [v for v in vals if v != 3] sur 200 000 listes aléatoires (longueurs 0 à 8, valeurs dans 0…3, donc listes entièrement à supprimer comprises) : 0 désaccord.
Les deux autres emplois. Fusionner deux listes triées : la sentinelle évite de traiter « le premier nœud du résultat » à part. Insérer avant la tête : même ligne que partout ailleurs. Dans les trois cas le gain est le même — un chemin de code au lieu de deux, donc une chance sur deux de bug en moins.
Où ça casse casse
Le cas fatal est silencieux : écraser cur.next avant d'avoir sauvé nxt. Rien ne plante, la boucle termine — plus vite, même — et renvoie une liste tronquée, parfaitement bien formée.
Le mécanisme : après cur.next = prev, lire nxt = cur.next donne prev. On repart donc en arrière dans le préfixe déjà inversé au lieu d'avancer dans le suffixe, et le suffixe n'est plus atteignable par personne.
« cur.next écrasé vaut prev, donc le pointeur suivant repart dans le préfixe, donc le suffixe devient inatteignable, donc la fonction rend une liste tronquée sans lever la moindre erreur. »
La ligne fautive. cur.next = prev puis nxt = cur.next, au lieu de l'ordre du pas 2.
Sur le fil rouge. 1 → 2 → 3 → 4 : tour 1, 1.next = ∅ puis nxt = 1.next = ∅, donc cur = ∅ et la boucle s'arrête au premier tour. Retour : [1] au lieu de [4, 3, 2, 1]. Mesuré pour n = 0…6 : la version fautive rend [], puis [1] pour tout n ≥ 1. Une liste valide, une longueur plausible, aucune exception.
Le variant l'attrape, l'invariant aussi. Le variant devrait perdre 1 par tour et il s'effondre d'un coup de n à 0. Et la seconde tranche de l'invariant du pas 3 — « cur est le suffixe intact » — est fausse dès le premier tour : cur désigne un nœud du préfixe. Dire l'invariant en entier suffit à voir le bug avant de lancer le code.
Le même silence, ailleurs. Renvoyer head au lieu de prev donne aussi [1] — même symptôme, autre cause. Et la boucle naïve du pas 6 rend [3, 1, 4] quand la réponse est [1, 4] : trois façons de rendre une liste bien formée et fausse.
Le test de trente secondes. Avant d'écrire la boucle : « après cette ligne, qui pointe encore vers le reste de la liste ? » Personne ⇒ le reste est perdu.
while fast.nextsansfast and. Sur une liste vide (fast = None) et sur toute longueur paire, rapide atterrit surNoneet l'itération suivante lèveAttributeError: 'NoneType' object has no attribute 'next'. Mesuré : ça plante pour n = 2, 4, 6 et passe pour n = 1, 3, 5 — donc un test sur une liste impaire ne voit rien. Écrirewhile fast and fast.next.- Retourner
headau lieu deprev. À la sortieheadest devenue la queue : on renvoie[1]. Pas d'erreur, juste une liste d'un élément. - Se passer de la sentinelle et traiter « supprimer la tête » à part : deux chemins de code, deux fois plus de bugs, et le cas « tout supprimer » (
3 → 3 → 3) oublié dans l'un des deux. - Le set de vus pour le cycle. Correct, O(n) en temps — et O(n) en mémoire : 32 Mo de table pour 106 nœuds, contre 16 octets. Le proposer est bien ; savoir dire pourquoi Floyd fait O(1) — l'écart +1 modulo L — est ce qui est attendu. Et comparer avec
is, jamais==: deux nœuds distincts peuvent porter la même valeur.
Résumé
- Signal : accès séquentiel, opération au milieu ou à l'envers, en place, O(1) espace. Contre-signal : accès aléatoire fréquent — prendre un tableau.
- Trois habits : lent / rapide, inversion en place, tête factice. Rien d'autre à retenir dans la famille.
- Inversion :
nxt = cur.nextpuiscur.next = prev; retourprev, jamaishead. - Invariant, avec ses deux tranches :
prev= inversion exacte de [tête,cur) etcur= suffixe [cur, fin) intact. Variant : longueur du suffixe, −1 par tour ⇒ n tours, O(1) espace. - Lent / rapide : rapide fait le double. Milieu (
while fast and fast.next⇒ le second milieu), k-ième depuis la fin (décalage de k, pas une vitesse), cycle. - Floyd : dans un cycle de longueur L, l'écart gagne 1 par tour modulo L, donc atteint 0. O(1) espace contre O(n) pour un set de vus.
- Casse silencieuse : écraser
cur.nextavant de sauvernxtrenvoie[1]pour toute liste non vide — bien formée, et fausse.
Chaîne verbalisée — une prise, à voix haute
- Énonce l'invariant de l'inversion — en entier.prev porte l'inversion exacte du préfixe [tête, cur), et cur porte le suffixe [cur, fin) intact. Les deux tranches, toujours : sans la seconde, rien n'interdit qu'un nœud ait été perdu en route.
- Pourquoi sauver
nxtavant d'écrirecur.next?cur.next est l'unique chemin vers le suffixe et l'affectation l'écrase. Sans nxt, on relit cur.next et on obtient prev : on repart en arrière, le suffixe est perdu, et la fonction renvoie [1] sans erreur. - Pourquoi lent et rapide se rencontrent-ils dans un cycle ?Une fois les deux dedans, rapide gagne un pas par tour sur lent, donc l'écart gagne 1 modulo la longueur du cycle, donc il passe par tous les résidus et atteint 0 en moins de L tours. Il ne peut pas sauter par-dessus : il change de 1, pas de 2.
- À quoi sert la tête factice, et que renvoie-t-on ?À donner un précédent à la tête, pour que supprimer ou insérer en tête ne soit plus un cas spécial : un seul chemin de code. On renvoie dummy.next, jamais head — head peut désigner un nœud supprimé.
- Cycle : Floyd ou un set de vus ? Défends ton choix.Même verdict, même O(n) en temps. Le set coûte O(n) en mémoire — 32 Mo de table pour un million de nœuds — contre deux pointeurs, 16 octets, pour Floyd. Et la comparaison se fait sur l'identité du nœud, avec is.
Ponts et cartes
coding::listes-chainees (le signal, les trois habits, l'inversion et son invariant à deux tranches) · coding::lent-rapide (la vitesse double, le second milieu, le k-ième comme écart figé) · coding::dummy-head (la sentinelle, dummy.next au retour, les trois emplois).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.