Description du Problème

Étant donné le nœud de tête d'une liste chaînée, déterminer le premier nœud qui introduit un cycle. Si aucun cycle n'existe, retourrner null.

Méthode 1 : Table de Hachage

Principe

Parcourir la liste chaînée en enregistrant chaque nœud dans une table de hachage. Lorsqu'un nœud déjà présent est rencontré, il s'agit du point d'entrée du cycle.

Implémentation

class Solution {
public:
    ListNode* findCycleEntry(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        std::unordered_set<ListNode*> nodeSet;
        ListNode* current = head;
        while (current != nullptr) {
            if (nodeSet.count(current)) {
                return current;
            }
            nodeSet.insert(current);
            current = current->next;
        }
        return nullptr;
    }
};

Complexité

• Temps : O(n)
• Espace : O(n) pour stocker les nœuds dans la table de hachage

Méthode 2 : Pointeurs Rapide-Lent avec Dérivation Mathématique

Principe

Cette méthode optimisée utilise deux étapes : d'abord, détecter un cycle à l'aide de pointeurs rapide et lent ; ensuite, localiser le point d'entrée par une déduction mathématique.

Étapes de l'algorithme

1. Initialiser deux pointeurs, l'un rapide (avancant de deux nœuds à la fois) et l'un lent (avancant d'un nœud).
2. Si un cycle existe, les pointeurs se rencontreront à un nœud intérieur au cycle.
3. Pour trouver le point d'entrée, déplacer un pointeur depuis la tête et un autre depuis le point de rencontre, tous deux à la même vitesse. Leur prochaine intersection correspondra au nœud d'entrée du cycle.

Démonstration Mathématique

Soit :

• a : distance du nœud de tête au point d'entrée du cycle.
• b : distance du point d'entrée au point de rencontre des pointeurs.
• c : longueur totale du cycle.

Lors de la rencontre, le pointeur lent a parcouru a + b nœuds, tandis que le pointeur rapide a parcouru a + b + k*c nœuds (k étant le nombre de tours de cycle). Puisque le pointeur rapide avance deux fois plus vite, on a : 2(a + b) = a + b + k*c, ce qui simplifie en a = k*c - b. Cette relation garantit qu'en avançant depuis la tête et le point de rencontre, les deux pointeurs convergeront au point d'entrée.

Implémentation Condensée

class Solution {
public:
    ListNode* findCycleEntry(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                ListNode* start = head;
                while (start != slow) {
                    start = start->next;
                    slow = slow->next;
                }
                return start;
            }
        }
        return nullptr;
    }
};

Implémentation Décomposée

class Solution {
public:
    ListNode* detectCycleNode(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        ListNode* fastPtr = head;
        ListNode* slowPtr = head;
        while (fastPtr != nullptr && fastPtr->next != nullptr) {
            fastPtr = fastPtr->next->next;
            slowPtr = slowPtr->next;
            if (fastPtr == slowPtr) {
                return fastPtr;
            }
        }
        return nullptr;
    }

    ListNode* findCycleEntry(ListNode* head) {
        ListNode* meetingPoint = detectCycleNode(head);
        if (meetingPoint == nullptr) {
            return nullptr;
        }
        ListNode* fromHead = head;
        ListNode* fromMeeting = meetingPoint;
        while (fromHead != fromMeeting) {
            fromHead = fromHead->next;
            fromMeeting = fromMeeting->next;
        }
        return fromHead;
    }
};

Complexité

• Temps : O(n)
• Espace : O(1) (utilisation minimale de pointeurs)