Question JavaScript intéressante : fusionner une sorte de liste chaînée

Tout le monde doit savoir que le tri par fusion est un processus consistant d'abord à diviser puis à fusionner.

Alors, comment fusionner et trier une liste à chaînage unique ?

Tout d'abord, nous avons besoin d'une méthode pour diviser la liste chaînée, comme indiqué dans le pseudocode suivant :

var source = 1 -> 3 -> 7 -> 8 -> 11 -> 12 -> 14 -> null  
var front = new Node()  
var back = new Node()  
frontBackSplit(source, front, back)  
front === 1 -> 3 -> 7 -> 8 -> null  
back === 11 -> 12 -> 14 -> null

Elle reçoit le pointeur de queue d'une liste chaînée en tant que paramètre et divise les éléments liés liste en un C'est deux, c'est-à-dire la première moitié et la seconde moitié.

Alors, comment déterminer cette valeur seuil intermédiaire ?

Vous pouvez utiliser des pointeurs rapides et lents. Le pointeur rapide et le pointeur lent partent de la queue en même temps et parcourent la liste à chaînage unique. Le pointeur rapide fait 2 pas à chaque fois et le pointeur lent en prend 1. pas à chaque fois. Ensuite, le pointeur rapide atteindra certainement la fin en premier, et le pointeur lent n'a parcouru que la moitié de la distance à ce moment-là, c'est-à-dire que le pointeur lent est exactement à cette position de division.

Le reste est facile à gérer, tronquez à la limite, définissez le paramètre sur null, et nous en avons terminé avec la première étape.

function Node(data) {  
    this.data = data === undefined ? null : data;  
    this.next = null;  
}  
  
function frontBackSplit(source, front, back) {  
    var total = 0;  
    var fast = source;  
    var slow = source;  
    var partial = null;  
    while(fast && fast.next){  
        fast = fast.next.next;  
        slow = slow.next;  
        total++;  
    }  
    partial = slow;  
    while(slow){  
        slow = slow.next;  
        total++;  
    }  
    if(total % 2 === 1){  
        back.data = partial.next.data;  
        back.next = partial.next.next;  
        partial.next = null;  
    }  
    else{  
        back.data = partial.data;  
        back.next = partial.next;  
        for(var e=source;e.next!=partial;e=e.next);  
        e.next = null;        
    }  
    front.data = source.data;  
    front.next = source.next;  
}

Ensuite, la liste chaînée est divisée et devient même des nœuds unitaires indivisibles. Nous devons trouver un moyen de les fusionner et de les assembler dans une nouvelle liste chaînée ordonnée. Par conséquent, nous avons besoin de ce qui suit. méthode de fusion :

var first = 2 -> 4 -> 6 -> 7 -> null  
var second = 1 -> 3 -> 5 -> 6 -> 8 -> null  
sortedMerge(first, second) === 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 6 -> 7 -> 8 -> null

Pour écrire une telle méthode, il y a en fait pas mal de cas à considérer, ce qui se reflète dans mon code :

function sortedMerge(l1, l2) {  
    var newList = null;  
    var temp = null;  
    while(l1 && l2){  
        if(l1.data > l2.data){  
            if(!newList){  
                newList = l2;  
                temp = l2;  
            }  
            else{  
                temp.next = l2;  
                temp = l2;  
            }  
            l2 = l2.next;  
        }  
        else{  
            if(!newList){  
                newList = l1;  
                temp = l1;  
            }  
            else{  
                temp.next = l1;  
                temp = l1;  
            }  
            l1 = l1.next;  
        }  
    }  
    if(l1){  
        if(!newList){  
            newList = l1;  
        }  
        else{  
            temp.next = l1;  
        }  
    }  
    if(l2){  
        if(!newList){  
            newList = l2;  
        }  
        else{  
            temp.next = l2;  
        }  
    }  
    return newList;  
}

D'accord, la division et les méthodes de fusion ont été écrites, tout comme la planche à découper et le couteau de cuisine sont prêts, il ne vous reste plus qu'à couper la viande. Méthode principale Il s'agit d'un processus récursif.

function mergeSort(list) {  
    if(list && list.next){  
        var front = new Node();  
        var back = new Node();  
        frontBackSplit(list, front, back);  
        return sortedMerge(mergeSort(front),mergeSort(back));  
    }  
    return list;  
}

Ce qui précède est la question JavaScript intéressante : le tri par fusion des listes chaînées. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !