Étant donné le nœud de tête d'une liste chaînée head, retournez le premier nœud où commence le cycle. Si aucune boucle n'existe, retournez null.

Une liste contient un cycle si un nœud peut être atteint à nouveau en suivant les pointeurs next de manière continue. Pour indiquer la présence d'un cycle, le système d'évaluation utilise un entier pos qui représente l'index (à partir de 0) où la fin de la liste est connectée à un nœud interne. Une valeur de pos = -1 signifie qu'il n'y a pas de cycle.

Remarque : pos n'est pas fourni en tant que paramètre ; il sert uniquement à représenter la structure interne. La modification de la liste n'est pas autorisée.

Exemple :

Entrée : head = [3,2,0,-4], pos = 1
Sortie : Retourne le nœud à l'index 1
Explication : La liste contient un cycle qui relie la dernière cellule au deuxième nœud.

Méthodologie :

Pour résoudre ce problème, deux étapes sont essentielles :

1. Détecter la présence d’un cycle : Utilisez deux pointeurs, l'un lent (slow) avançant d'un pas à la fois, l'autre rapide (fast) avançant de deux pas. Si un cycle existe, le pointeur rapide rattrapera toujours le lent.
2. Localiser le début du cycle : Une fois les deux pionteurs en collision, placez un nouveau pointeur au début de la liste et faites-en avancer un autre depuis le point de collision, tous deux d’un pas par itération. Le point où ils se rejoignent crorespond au début du cycle.

Soit x la distance entre le début de la liste et le point d’entrée du cycle. Soit y la distance entre le point d’entrée et le point de rencontre des pointeurs. Soit z la distance restante pour revenir au point d’entrée depuis le point de collision. En supposant que le pointeur rapide a parcouru n tours complets dans le cycle avant de rattraper le lent, on obtient :

• Distance parcourue par slow : x + y
• Distance parcourue par fast : x + y + n(y + z)

Comme fast avance deux fois plus vite que slow, on a :

2(x + y) = x + y + n(y + z)
→ x + y = n(y + z)
→ x = (n - 1)(y + z) + z

Lorsque n = 1, cela devient x = z. Cela implique que si l'on démarre un pointeur depuis le début de la liste et un autre depuis le point de collision, ils se rencontreront exactement au début du cycle après un nombre égal d'étapes.

Si n > 1, le pointeur rapide a fait plusieurs tours supplémentaires, mais le résultat reste valable : les deux pointeurs se croisent toujours au début du cycle, même si l’un a fait des tours supplémentaires.

La logique fondamentale repose sur le fait que, dès que slow entre dans le cycle, fast est déjà à l’intérieur. Leur vitesse relative garantit qu'ils se croisent avant que slow ne fasse une boucle complète.

Implémentation :

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        // Détection du cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                // Cycle détecté : localisation du point d'entrée
                ListNode ptr1 = head;
                ListNode ptr2 = slow;

                while (ptr1 != ptr2) {
                    ptr1 = ptr1.next;
                    ptr2 = ptr2.next;
                }
                return ptr1;
            }
        }

        return null;
    }
}