Ausführliche Erklärung zum Zusammenführen geordneter verknüpfter Listen in JavaScript

Für das Problem der Zusammenführung zweier geordneter verknüpfter Listen zu einer geordneten verknüpften Liste wird in Yan Weimins Version von „Data Structure“ ein klassischer Algorithmus verwendet.

1. Verwenden Sie zwei Zeiger, um auf die Knoten zu zeigen, die derzeit in den beiden verknüpften Listen verglichen werden sollen, und erstellen Sie eine neue verknüpfte Liste, um die Knoten in den beiden verknüpften Listen zu speichern.

2. Bei jedem Vergleich der Größe des Knotenelements wird der kleinere Elementknoten in die neue verknüpfte Liste eingefügt und der Zeiger wird so lange nach hinten verschoben, bis einer der Zeiger leer ist.

3. Zeigen Sie mit einem weiteren Nicht-Null-Zeiger auf den verbleibenden Teil der verknüpften Liste. Nach der Verknüpfung mit der neuen verknüpften Liste ist der Zusammenführungsprozess abgeschlossen.

Dieser Algorithmus ist sehr effizient, er ist O(m+n), aber er muss eine neue verknüpfte Liste erstellen.

Angenommen, ich habe eine solche Anforderung:

1. Führen Sie die zweite verknüpfte Liste mit der ersten verknüpften Liste zusammen, sodass keine neue verknüpfte Liste generiert werden kann.

2. Die Referenzbeziehung des zweiten verknüpften Listenknotens kann nicht geändert werden, d. h. sie kann sich nicht auf die zweite verknüpfte Liste auswirken.

Was tun?

Für dieses Problem gibt es 3 Analysepunkte:

1 Dies ist eine Methode zum Einfügen des zweiten verknüpften Listenelements in die erste Frage zur verknüpften Liste.

2. Der eingefügte Knoten kann nicht der ursprüngliche Knoten der zweiten verknüpften Liste sein, sondern ein neuer Knoten, da er sich sonst auf die zweite verknüpfte Liste auswirkt.

3.Die äußere Schleife steuert das Durchlaufen der zweiten verknüpften Liste, und die innere Schleife ist für das Einfügen neuer Knoten verantwortlich, es handelt sich also um einen Algorithmus von O(m*n) .

Detaillierte Umsetzung:

//将l2合并到l1
var mergeTwoLists = function(l1, l2) {
	//遍历l2链表，将元素一一插入l1
    while(l2){
		//先前的l1元素
        var prev = null;
		//当前的l1元素
        var cur = l1;
		//遍历l1链表，找到可插入l2元素的位置
        while(cur && l2.val > cur.val){
			//记录先前的l1元素
            prev = cur;
			//记录当前的l1元素
            cur = cur.next;
        }
		//生成新的节点
		//注意：并没有利用l2已有的节点
        var newNode = new ListNode(l2.val);
		//插入新节点
		//新节点的next指向当前的l1元素
        newNode.next = cur;
		//如果是在l1链表中间插入
		//或者说新节点有前驱
        if(prev){
			//先前元素的next指向新节点
            prev.next = newNode;
        }//如果新节点插在链表头部
        else{
            l1 = newNode;
        }
        l2 = l2.next;
    }
	//返回l1
    return l1;
};

Das obige ist der detaillierte Inhalt vonAusführliche Erklärung zum Zusammenführen geordneter verknüpfter Listen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!