0Pricing
DSA Interview Prep · Leçon

Fusionner, scinder et trouver le n-ième élément depuis la fin

Fusionnez deux listes chaînées triées en O(n), scindez une liste à son point médian avec des pointeurs lent et rapide, puis trouvez le n-ième nœud depuis la fin.

Fusionner, scinder et trouver le n-ième élément depuis la fin est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.

Trois modèles essentiels des listes chaînées

Cette leçon couvre trois opérations fondamentales sur les listes chaînées, qui servent constamment de briques dans des problèmes plus difficiles : fusionner deux listes triées (pour le tri fusion et la fusion à k voies), séparer une liste à son point médian (pour le tri fusion et la détection de palindromes) et trouver le nœud en n-ième position depuis la fin (pour supprimer le nœud en n-ième position depuis la fin).

Ces trois opérations reposent sur des techniques que vous avez déjà vues : le nœud de tête factice, les pointeurs lent et rapide et le suivi attentif des limites.

Fusionner deux listes triées

LeetCode 21, « Fusionner deux listes triées » : étant donné deux listes chaînées triées, renvoyez une seule liste triée issue de leur fusion. Utilisez une tête factice et un pointeur de queue curr. À chaque étape, comparez les têtes des deux listes et rattachez le plus petit nœud à curr. Lorsqu'une liste est épuisée, rattachez le reste de l'autre. Temps : O(n+m), espace : O(1) (réorganisation sur place des liens).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2  # attach remaining nodes
    return dummy.next

def build(arr):
    d = ListNode(); c = d
    for v in arr:
        c.next = ListNode(v); c = c.next
    return d.next

def to_list(h):
    r=[]
    while h: r.append(h.val); h=h.next
    return r

print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))

Suivre la fusion pas à pas

Suivez mergeTwoLists([1,2,4], [1,3,4]) : comparez 1 et 1 — choisissez l1(1), avancez l1 jusqu'à 2. Comparez 2 et 1 — choisissez l2(1), avancez l2 jusqu'à 3. Comparez 2 et 3 — choisissez l1(2), avancez l1 jusqu'à 4. Comparez 4 et 3 — choisissez l2(3), avancez l2 jusqu'à 4. Comparez 4 et 4 — choisissez l1(4), avancez l1 jusqu'à None. Rattachez le l2(4) restant. Résultat : [1,1,2,3,4,4].

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    step  = 0
    while l1 and l2:
        step += 1
        if l1.val <= l2.val:
            print(f'Step {step}: pick l1({l1.val})')
            curr.next = l1; l1 = l1.next
        else:
            print(f'Step {step}: pick l2({l2.val})')
            curr.next = l2; l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next

mergeTwoLists(build([1,2,4]),build([1,3,4]))

Trouver le milieu avec les pointeurs lent et rapide

Pour séparer une liste à son point médian, utilisez le modèle des pointeurs lent et rapide. slow avance d'une étape ; fast avance de deux étapes. Lorsque fast atteint la valeur nulle (ou le dernier nœud), slow se trouve au milieu. Pour une liste de longueur paire, cela donne le premier des deux nœuds centraux, ce qui est la convention utilisée pour séparer une liste lors d'un tri fusion.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def split_at_mid(head):
    '''Returns (first_half_head, second_half_head).'''
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next   # second half starts here
    slow.next = None  # sever the list
    return head, mid

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next

def to_list(h):
    r=[]
    while h: r.append(h.val); h=h.next
    return r

head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second))  # [1,2,3] [4,5]

Tri par fusion d’une liste chaînée

LeetCode 148 « Trier une liste » : trier une liste chaînée en O(n log n) avec une complexité temporelle de O(n log n) et une complexité spatiale de O(log n). La méthode consiste à couper la liste au niveau du milieu, à trier récursivement chaque moitié, puis à les fusionner. Le tri par fusion d’une liste chaînée est naturel, car la séparation au milieu coûte O(n) (et non O(1) comme avec les tableaux), mais la complexité globale reste O(n log n), avec seulement O(log n) d’espace dans la pile d’appels.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sortList(head):
    if not head or not head.next:
        return head
    # Split
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    # Recurse
    left  = sortList(head)
    right = sortList(mid)
    # Merge
    dummy = ListNode(0)
    curr  = dummy
    while left and right:
        if left.val <= right.val:
            curr.next = left;  left  = left.next
        else:
            curr.next = right; right = right.next
        curr = curr.next
    curr.next = left or right
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(sortList(build([4,2,1,3]))))  # [1,2,3,4]

Trouver le n-ième nœud depuis la fin

LeetCode 19 « Supprimer le n-ième nœud depuis la fin de la liste » : trouver le n-ième nœud depuis la fin en un seul parcours. Utilisez deux pointeurs séparés exactement de n nœuds. Avancez fast de n étapes devant slow. Avancez ensuite les deux pointeurs ensemble jusqu’à ce que le pointeur rapide atteigne le dernier nœud. À ce moment-là, le pointeur lent se trouve sur le (n+1)-ième nœud depuis la fin, c’est-à-dire le prédécesseur du nœud à supprimer.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    for _ in range(n + 1):  # advance fast n+1 steps
        fast = fast.next
    slow = dummy
    while fast:             # advance both until fast is None
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next  # remove nth node
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2)))  # [1,2,3,5]

Pourquoi n+1 étapes pour supprimer le n-ième nœud

La subtilité essentielle consiste à faire avancer le pointeur rapide de n+1 étapes (et non n) depuis la tête factice. Après n+1 étapes, le pointeur rapide a n+1 positions d’avance sur le pointeur lent (les deux partant de la tête factice). Lorsque le pointeur rapide atteint la valeur nulle (une position après la fin), le pointeur lent se trouve n+1 positions avant cette valeur nulle — ce qui signifie qu’il est à la position (longueur - n - 1) en partant de zéro, autrement dit sur le prédécesseur de la cible. Cela permet à slow.next = slow.next.next de supprimer proprement le n-ième nœud depuis la fin.

# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow)  1  2  3(fast)  4  5  None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')

Intersection de deux listes chaînées

LeetCode 160 « Intersection de deux listes chaînées » : trouver le nœud où deux listes se rencontrent pour la première fois. L’astuce utilisant O(1) espace consiste à faire avancer deux pointeurs, un par liste. Lorsqu’un pointeur atteint la fin, redirigez-le vers la tête de l’autre liste. Après au plus longueur(A) + longueur(B) étapes, les deux pointeurs ont parcouru la même distance totale et doivent se trouver sur le nœud d’intersection (ou tous deux à la fin s’il n’y a pas d’intersection).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getIntersectionNode(headA, headB):
    a, b = headA, headB
    while a is not b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a  # None if no intersection

# Build: A: 4->1->\  B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val)  # 8

Fusionner K listes triées (diviser pour régner)

LeetCode 23 « Fusionner K listes triées » : étant donné k listes triées, les fusionner en une seule. L’approche optimale consiste à fusionner régulièrement des paires de listes en utilisant la méthode diviser pour régner, ce qui divise par deux le nombre de listes à chaque tour. Avec k listes de longueur moyenne n, cette méthode prend O(n k log k) en temps, contre O(n k²) pour des fusions séquentielles. Une approche avec un tas minimal est également en O(n k log k).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    def merge_two(l1, l2):
        dummy = ListNode(0); curr = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1; l1 = l1.next
            else:
                curr.next = l2; l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

    if not lists: return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i+1] if i+1 < len(lists) else None
            merged.append(merge_two(l1, l2))
        lists = merged
    return lists[0]

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists)))  # [1,1,2,3,4,4,5,6]

Liste chaînée des nœuds impairs et pairs

LeetCode 328 « Liste chaînée des nœuds impairs et pairs » : regrouper d’abord tous les nœuds d’indice impair, puis ceux d’indice pair (avec des indices commençant à 1). La méthode consiste à maintenir deux chaînes distinctes (impaires et paires), puis à les relier une fois le parcours terminé. Un seul parcours de la liste suffit, ce qui donne une complexité temporelle de O(n) et une complexité spatiale de O(1). C’est un exemple clair de progression simultanée de deux pointeurs avec des pas différents.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head):
    if not head:
        return head
    odd  = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next  = even.next
        odd       = odd.next
        even.next = odd.next
        even      = even.next
    odd.next = even_head
    return head

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(oddEvenList(build([1,2,3,4,5]))))  # [1,3,5,2,4]

Mise en pratique

Les trois schémas de cette leçon — fusionner des listes triées, couper au niveau du milieu et trouver le n-ième nœud depuis la fin — reposent sur une idée commune : utiliser des variables de pointeur supplémentaires pour suivre les positions sans mémoire additionnelle. La tête factice simplifie la fusion et la suppression ; l’écart entre les pointeurs lent et rapide fixe une position relative précise ; faire avancer un pointeur en premier crée la séparation souhaitée.

Lors d’un entretien, nommez le schéma que vous utilisez avant de coder : « Je vais utiliser la technique de l’écart entre deux pointeurs pour trouver le n-ième nœud depuis la fin en un seul parcours. » Cela démontre une réflexion structurée.

Vérification rapide

Testez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que : la fusion de deux listes triées utilise une tête factice et une comparaison à chaque étape, pour une complexité O(n+m) et un espace O(1), la séparation au milieu utilise les pointeurs lent et rapide, le pointeur rapide s’arrêtant sur le dernier couple valide, et la recherche du n-ième nœud depuis la fin fait avancer le pointeur rapide de n+1 étapes afin que le pointeur lent se retrouve sur le prédécesseur. Ensuite, vous construirez des piles et des files et les appliquerez à des problèmes classiques d’entretien.

Questions Fréquemment Posées

La leçon « Fusionner, scinder et trouver le n-ième élément depuis la fin » est-elle gratuite ?

Oui — le texte complet de « Fusionner, scinder et trouver le n-ième élément depuis la fin » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Fusionner, scinder et trouver le n-ième élément depuis la fin » ?

Fusionnez deux listes chaînées triées en O(n), scindez une liste à son point médian avec des pointeurs lent et rapide, puis trouvez le n-ième nœud depuis la fin. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?

Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Fusionner, scinder et trouver le n-ième élément depuis la fin » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?

Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Classe Node et construction de listes
  2. Inverser une liste chaînée
  3. Détection de cycles avec l’algorithme de Floyd
  4. Fusionner, scinder et trouver le n-ième élément depuis la fin
← Retour à DSA Interview Prep