Listes chaînées : rapides à modifier, lentes à parcourir

L'inverse exact du tableau : insertion en O(1) une fois le nœud atteint, mais accès par index en O(n).

Chaque nœud contient une valeur et un pointeur vers le suivant (simple) ou vers le suivant et le précédent (double). Rebrancher des pointeurs suffit pour insérer ou supprimer.

Inverser une liste#

La technique à maîtriser : trois variables (prev, curr, next), O(n) temps, O(1) espace.

class ListNode {
  constructor(public val: number, public next: ListNode | null = null) {}
}

function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr) {
    const next = curr.next;                         // sauvegarder AVANT de casser le lien
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

Détecter un cycle : lent et rapide (Floyd)#

Le pointeur rapide avance de 2, le lent de 1. S'il y a un cycle, ils finissent par se rencontrer.

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;                                     // O(n) temps, O(1) espace
}

Piège : perdre le reste de la liste en réassignant next trop tôt. Sauvegardez toujours le nœud suivant dans une variable temporaire. Utilisez aussi un nœud sentinelle (dummy) en tête quand la tête peut changer : il évite les cas particuliers.

Pour aller plus loin#

• Reverse Linked List — Iterative AND Recursive (Leetcode 206) — NeetCode