Sort List

+10

Tu reçois une liste simplement chaînée stockée dans deux tableaux de même longueur. Le nœud i contient la valeur values[i] et pointe vers le nœud next[i], -1 marque la fin de la liste, et la tête est le nœud 0. Les nœuds ne sont pas stockés dans l’ordre de la liste, et les tableaux peuvent également contenir des nœuds restants que le parcours à partir du nœud 0 n’atteint jamais. Ceux-ci ne font pas partie de la liste, même lorsque leurs liens pointent vers elle.

Trie la liste par ordre non décroissant de valeur et renvoie les valeurs de ses nœuds dans cet ordre.

Fonction

sortList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: l’indice du nœud vers lequel chaque nœud pointe, ou -1 pour le dernier nœud
valuesinteger-array: la valeur détenue par chaque nœud
Renvoieinteger-array: les valeurs des nœuds de la liste, de la plus petite à la plus grande

Contraintes

1 ≤ n ≤ 4000, où n est la longueur de next et de values.
-1000 ≤ values[i] ≤ 1000
Chaque next[i] vaut -1 ou un indice de nœud compris entre 0 et n-1.
En partant du nœud 0, la liste atteint -1 sans visiter deux fois un nœud.
Les nœuds que le parcours depuis le nœud 0 n’atteint pas ne font pas partie de la liste. Leurs entrées next peuvent pointer n’importe où.

Exemples

Entrée: next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
Sortie: [1, 2, 3, 4, 5]
Explication: Le parcours à partir du nœud 0 visite les nœuds 0, 3, 2, 4, 1, donc la liste est 4, 2, 3, 5, 1. Triée, elle donne 1, 2, 3, 4, 5.

Entrée: next = [2, 0, -1, -1]values = [6, 9, -2, 5]
Sortie: [-2, 6]
Explication: La liste est 0 → 2, ce qui donne 6, -2. Les nœuds 1 et 3 ne sont jamais atteints depuis la tête, donc leurs valeurs 9 et 5 sont omises, même si le nœud 1 pointe vers le nœud 0.

Entrée: next = [1, 2, 3, -1]values = [3, -1, 3, -1]
Sortie: [-1, -1, 3, 3]
Explication: La liste contient 3, -1, 3, -1. Les valeurs égales restent dans la réponse autant de fois qu’elles apparaissent : -1, -1, 3, 3.

Pour aller plus loin

Peux-tu trier en reliant à nouveau les nœuds en O(n log n), sans copier les valeurs ?

Solution

Quicksort et heapsort reposent sur l’accès aléatoire, et une liste simplement chaînée ne se parcourt que vers l’avant. Le tri fusion convient : couper une liste en son milieu et fusionner deux listes triées nécessitent toutes deux de parcourir la liste vers l’avant, ce qui permet de trier les liens eux-mêmes en O(n log n). Ici, n représente la longueur des tableaux.

Copiez les valeurs dans un tableau et triez-le

Intuition

La liste correspond à ce que le parcours node = next[node] visite depuis le nœud 0 jusqu’à -1. Récupérez ces valeurs dans un nouveau tableau, triez-le avec la fonction de tri intégrée et renvoyez-le. Vous ne pouvez pas trier directement values : dans le deuxième exemple, il contient 9 et 5, qui ne figurent pas dans la liste.

Le parcours est en O(n) et le tri en O(n log n), avec une mémoire supplémentaire de O(n). La liste elle-même n’est jamais modifiée, c’est pourquoi les recruteurs demandent l’approche suivante.

Algorithme

Commence avec un tableau vide et node = 0.
Tant que node n’est pas -1, ajoute values[node] et passe à next[node].
Trie le tableau par ordre croissant et renvoie-le.

def sortList(next, values):
    # Collect the values of the nodes on the list, then sort them.
    on_list = []
    node = 0
    while node != -1:
        on_list.append(values[node])
        node = next[node]
    on_list.sort()
    return on_list

Tri par fusion sur les liens

Intuition

Un pointeur lent qui avance d’un maillon et un pointeur rapide qui en avance de deux trouvent le milieu en un seul parcours. Pour fusionner deux listes triées, seuls leurs nœuds de tête sont nécessaires : prenez le plus petit et avancez. Aucune de ces étapes ne nécessite de tableau supplémentaire.

Dans le premier exemple, slow s’arrête sur le 3, et couper son lien sépare 4, 2, 3, 5, 1 en 4, 2, 3 et 5, 1. Ces listes sont triées en 2, 3, 4 et 1, 5, puis la fusion prend 1, 2, 3, 4, avant de relier le 5 restant.

À chaque niveau de division, chaque nœud est traité un nombre constant de fois, et il y a environ log n niveaux, donc le temps d’exécution est de O(n log n). La seule mémoire supplémentaire utilisée est la pile de récursion, d’environ 12 appels de profondeur pour 4000 nœuds.

Algorithme

Si la liste contient un seul nœud (next[head] == -1), renvoie head.
Initialise slow = head et fast = next[head] ; avance slow d’un lien et fast de deux liens tant que fast et next[fast] ne valent pas -1.
Définis second = next[slow] et coupe la liste avec next[slow] = -1.
Trie récursivement les deux moitiés. Fusionne-les : relie le plus petit nœud en tête après tail jusqu’à ce qu’une moitié soit vide, puis relie le reste de l’autre moitié.
Parcours la liste à partir de la tête renvoyée et récupère les valeurs.

def sortList(next, values):
    def merge(a, b):
        # Splice two sorted lists into one; on a tie the node from a goes first.
        head = tail = -1
        while a != -1 and b != -1:
            if values[b] < values[a]:
                node, b = b, next[b]
            else:
                node, a = a, next[a]
            if tail == -1:
                head = node
            else:
                next[tail] = node
            tail = node
        next[tail] = a if a != -1 else b  # attach whatever is left
        return head

    def sort(head):
        if next[head] == -1:  # one node is already sorted
            return head
        # slow stops on the last node of the first half
        slow, fast = head, next[head]
        while fast != -1 and next[fast] != -1:
            slow = next[slow]
            fast = next[next[fast]]
        second = next[slow]
        next[slow] = -1  # cut the list in two
        return merge(sort(head), sort(second))

    result = []
    node = sort(0)
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Pièges et cas limites

Trier tout le tableau values. Dans le deuxième exemple, cela fait apparaître 9 et 5, qui ne sont pas dans la liste.
Commencer fast sur la tête. Avec deux nœuds, slow arrive alors sur le deuxième nœud, la coupure laisse une seconde moitié vide et la récursion ne réduit jamais la taille de la liste.
Oublier la coupure next[slow] = -1. La première moitié rejoint alors la seconde, et les deux appels trient des listes qui se chevauchent.
Supprimer le reste d’une moitié lorsque l’autre est épuisée. Ces nœuds disparaissent du résultat.
En Lua et en R, les tableaux commencent à 1 : conservez les indices des nœuds à partir de 0 et lisez next[node + 1]. La version R copie le tableau de liens une seule fois, donc elle utilise O(n) de mémoire supplémentaire.

Questions fréquentes3

Quelle est la meilleure façon de trier une liste chaînée ?

Tri fusion. La division au milieu, le tri des deux moitiés et leur fusion parcourent tous la liste vers l’avant, la seule direction prise en charge par une liste simplement chaînée. Elle s’exécute en O(n log n) et réorganise les liens entre les nœuds existants.

Pourquoi le tri fusion est-il préféré au tri rapide pour les listes chaînées ?

Quicksort peut partitionner une liste en réorganisant les liens, mais un bon pivot nécessite un accès aléatoire, et choisir la tête comme pivot donne un coût de O(n²) pour une liste triée. Le tri fusion divise toujours en deux, il reste donc en O(n log n) quel que soit l’entrée.

Pouvez-vous trier une liste chaînée en temps O(n log n) et en mémoire O(1) ?

Oui, avec le tri fusion ascendant. Il fusionne les séquences voisines de longueur 1, puis 2, puis 4, jusqu’à ce qu’une seule séquence couvre la liste. Il y a log n passes linéaires, et la seule mémoire utilisée se limite à quelques index de nœuds.

def sortList(next, values):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

next = [3, -1, 4, 2, 1]
values = [4, 1, 3, 2, 5]

Résultat attendu

[1, 2, 3, 4, 5]