Interessante JavaScript-Frage: Art verknüpfter Liste zusammenführen

Jeder muss wissen, dass die Zusammenführungssortierung ein Prozess ist, bei dem zuerst geteilt und dann zusammengeführt wird.

Wie kann man also eine einfach verknüpfte Liste zusammenführen und sortieren?

Zuerst benötigen wir eine Methode zum Teilen der verknüpften Liste, wie im folgenden Pseudocode gezeigt:

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

Sie empfängt den Endzeiger einer verknüpften Liste als Parameter und teilt die verknüpfte Liste Liste in eins Es sind zwei, also die erste Hälfte und die zweite Hälfte.

Wie lässt sich also dieser Zwischengrenzwert bestimmen?

Sie können schnelle und langsame Zeiger gleichzeitig am Ende verwenden und die einfach verknüpfte Liste durchlaufen. Der schnelle Zeiger benötigt jeweils 2 Schritte und der langsame Zeiger benötigt 1 Dann erreicht der schnelle Zeiger mit Sicherheit zuerst das Ende und der langsame Zeiger hat zu diesem Zeitpunkt erst die halbe Strecke zurückgelegt, d. h. der langsame Zeiger befindet sich genau an dieser Teilungsposition.

Der Rest ist einfach zu handhaben: An der Grenze abschneiden, die Einstellung auf Null setzen und schon sind wir mit der ersten Stufe fertig.

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;  
}

Dann wird die verknüpfte Liste aufgelöst und wird sogar zu unteilbaren Einheitsknoten. Wir müssen einen Weg finden, sie zusammenzuführen und zu einer neuen geordneten verknüpften Liste zusammenzusetzen Zusammenführungsmethode:

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

Um eine solche Methode zu schreiben, müssen tatsächlich viele Fälle berücksichtigt werden, was sich in meinem Code widerspiegelt:

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;  
}

Okay, das Teilen und Die Zubereitungsmethoden sind aufgeschrieben, Schneidebrett und Küchenmesser liegen bereit, Sie müssen nur noch das Fleisch schneiden. Hauptmethode Dies ist ein rekursiver Prozess.

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;  
}

Das Obige ist die interessante JavaScript-Frage: Sortierung verknüpfter Listen zusammenführen. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn)!