Suppression et Filtrage de Nœuds

La manipulation des pointeurs est fondamentale lors de la suppression de nœuds dans une liste chaînée. Pour une liste sans nœud d'en-tête, l'approche récursive offre une élégance particulière en modifiant directement les références via des pointeurs sur pointeurs. Pour les listes avec nœud d'en-tête, une approche itérative avec un pointeur précédent est généralement préférable pour des raisons de performance et de débogage.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// Suppression récursive pour une liste sans nœud d'en-tête
void deleteValueRecursive(ListNode **headRef, int target) {
    if (*headRef == NULL) return;
    
    ListNode *current = *headRef;
    if (current->val == target) {
        *headRef = current->next;
        free(current);
        deleteValueRecursive(headRef, target);
    } else {
        deleteValueRecursive(&(current->next), target);
    }
}

// Suppression itérative pour une liste avec nœud d'en-tête
void deleteValueIterative(ListNode *head, int target) {
    ListNode *prev = head;
    ListNode *curr = head ? head->next : NULL;
    
    while (curr != NULL) {
        if (curr->val == target) {
            prev->next = curr->next;
            free(curr);
            curr = prev->next;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
}

// Suppression des doublons dans une liste triée
void removeSortedDuplicates(ListNode *head) {
    ListNode *curr = head ? head->next : NULL;
    while (curr != NULL && curr->next != NULL) {
        if (curr->val == curr->next->val) {
            ListNode *duplicate = curr->next;
            curr->next = duplicate->next;
            free(duplicate);
        } else {
            curr = curr->next;
        }
    }
}

Inversion, Tri et Fusion

L'inversion d'une liste chaînée sur place (complexité spatiale O(1)) est une opération classique qui nécessite de maintenir trois pointeurs pour ne pas perdre la référence au reste de la liste. Le tri fusion est l'algorithme de tri le plus adapté aux listes chaînées, car il évite les accès aléatoires coûteux et s'intègre parfaitement à la structure linéaire des nœuds.

// Inversion sur place d'une liste avec nœud d'en-tête
void reverseListInPlace(ListNode *head) {
    if (!head || !head->next) return;
    
    ListNode *prev = NULL;
    ListNode *curr = head->next;
    ListNode *nextNode = NULL;
    
    while (curr != NULL) {
        nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }
    head->next = prev;
}

// Fusion de deux listes triées
ListNode* mergeSortedLists(ListNode *l1, ListNode *l2) {
    ListNode dummy;
    ListNode *tail = &dummy;
    
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = (l1 != NULL) ? l1 : l2;
    return dummy.next;
}

// Trouver le milieu de la liste pour le tri fusion
ListNode* getMiddleNode(ListNode *head) {
    if (!head) return NULL;
    ListNode *slow = head;
    ListNode *fast = head->next;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Tri fusion récursif
ListNode* mergeSort(ListNode *head) {
    if (!head || !head->next) return head;
    
    ListNode *mid = getMiddleNode(head);
    ListNode *rightHead = mid->next;
    mid->next = NULL; // Couper la liste en deux
    
    ListNode *left = mergeSort(head);
    ListNode *right = mergeSort(rightHead);
    
    return mergeSortedLists(left, right);
}

Techniques de Pointeurs Multiples (Rapide et Lent)

L'utilisation de pointeurs rapides et lents (algorithme de Floyd) est cruciale pour résoudre des problèmes tels que la détection de cycles, la recherche du k-ième nœud depuis la fin, ou la détermination du nœud d'intersection de deux listes. Ces approches permettent de réduire la complexité temporelle et d'éviter l'utilisation de structures de données auxiliaires.

// Détection de cycle (Tortue et Lièvre)
bool hasCycle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// Trouver le k-ième nœud depuis la fin
ListNode* findKthFromEnd(ListNode *head, int k) {
    ListNode *fast = head;
    ListNode *slow = head;
    
    for (int i = 0; i < k; i++) {
        if (fast == NULL) return NULL; // k est supérieur à la longueur
        fast = fast->next;
    }
    
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

// Trouver le nœud d'intersection de deux listes
ListNode* getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (!headA || !headB) return NULL;
    
    ListNode *ptrA = headA;
    ListNode *ptrB = headB;
    
    while (ptrA != ptrB) {
        ptrA = (ptrA == NULL) ? headB : ptrA->next;
        ptrB = (ptrB == NULL) ? headA : ptrB->next;
    }
    return ptrA;
}

Listes Doublement Chaînées et Circulaires

Les listes doublement chaînées circulaires ajoutent une couche de cmoplexité mais offrent des avantages pour certaines opérations, comme la vérification de symétrie ou la gestion de caches basés sur la fréquence d'accès (LFU). La manipulation des pointeurs prev et next doit être effectuée avec une rigueur extrême pour éviter les fuites de mémoire ou les boucles infinies.

typedef struct DListNode {
    int val;
    struct DListNode *prev;
    struct DListNode *next;
    int freq;
} DListNode;

// Vérifier la symétrie d'une liste doublement chaînée circulaire
bool isCircularDoublySymmetric(DListNode *head) {
    if (!head || !head->next || head->next == head) return true;
    
    DListNode *left = head->next;
    DListNode *right = head->prev;
    
    while (left != right && left->prev != right) {
        if (left->val != right->val) return false;
        left = left->next;
        right = right->prev;
    }
    return true;
}

// Accéder à un nœud et réorganiser la liste selon la fréquence (LFU)
DListNode* accessAndReorderNode(DListNode *head, int target) {
    DListNode *curr = head->next;
    while (curr != NULL && curr->val != target) {
        curr = curr->next;
    }
    if (curr == NULL) return NULL;

    curr->freq++;
    DListNode *prevNode = curr->prev;

    // Si le nœud est déjà au bon endroit ou en tête
    if (prevNode == head || prevNode->freq > curr->freq) {
        return curr;
    }

    // Détacher le nœud courant
    prevNode->next = curr->next;
    if (curr->next != NULL) {
        curr->next->prev = prevNode;
    }

    // Trouver la nouvelle position d'insertion
    while (prevNode->prev != head && prevNode->prev->freq <= curr->freq) {
        prevNode = prevNode->prev;
    }

    // Réinsérer le nœud
    curr->next = prevNode->next;
    curr->prev = prevNode;
    if (prevNode->next != NULL) {
        prevNode->next->prev = curr;
    }
    prevNode->next = curr;

    return curr;
}