Explication détaillée de la fusion de listes chaînées ordonnées en JavaScript

Pour le problème de la fusion de deux listes chaînées ordonnées en une seule liste chaînée ordonnée, un algorithme classique est utilisé dans la version de Yan Weimin de "Data Structure".

1. Utilisez deux pointeurs pour pointer vers les nœuds actuellement à comparer dans les deux listes chaînées et créez une nouvelle liste chaînée pour stocker les nœuds dans les deux listes chaînées.

2. Chaque fois que la taille de l'élément nœud est comparée, le nœud d'élément le plus petit est introduit dans la nouvelle liste chaînée et le pointeur est déplacé vers l'arrière. Ce processus se poursuit jusqu'à ce que l'un des pointeurs soit vide.

3. Pointez un autre pointeur non nul vers la partie restante de la liste chaînée, et après la liaison vers la nouvelle liste chaînée, le processus de fusion est terminé.

Cet algorithme est très efficace et est O(m n), mais il nécessite de créer une nouvelle liste chaînée.

Supposons que j'ai une telle exigence :

1. Fusionner la deuxième liste chaînée dans la première liste chaînée, exigeant qu'aucune nouvelle liste chaînée ne puisse être générée.

2. La relation de référence du deuxième nœud de liste chaînée ne peut pas être modifiée, ou en d'autres termes, elle ne peut pas affecter la deuxième liste chaînée.

Que faire ?

Pour ce problème, il y a 3 points d'analyse :

1 Il s'agit d'une méthode d'insertion du deuxième élément de liste chaînée dans le. première question de liste chaînée.

2. Le nœud inséré ne peut pas être le nœud d'origine de la deuxième liste chaînée, mais un nouveau nœud, sinon cela affectera la deuxième liste chaînée.

3.La boucle externe contrôle la traversée de la deuxième liste chaînée, et la boucle interne est responsable de l'insertion de nouveaux nœuds, c'est donc un algorithme de O(m*n) .

Mise en œuvre détaillée :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!