JavaScript での順序付きリンク リストのマージの詳細な説明

2 つの順序付きリンク リストを 1 つの順序付きリンク リストにマージする問題については、Yan Weimin バージョンの「データ構造」で古典的なアルゴリズムが使用されています。

1. 2 つのポインターを使用して、2 つのリンク リストで現在比較されるノードを指し、新しいリンク リストを作成して、2 つのリンク リストにノードを保存します。

2. ノード要素のサイズが比較されるたびに、小さい方の要素ノードが新しいリンク リストに導入され、ポインターが後方に移動します。このプロセスは、ポインターの 1 つが空になるまで続けられます。

3. 別の非 null ポインターをリンク リストの残りの部分にポイントし、新しいリンク リストにリンクした後、マージ プロセスが完了します。

このアルゴリズムは非常に効率的でO(m+n)ですが、新しいリンクリストを作成する必要があります。

次のような要件があるとします。

1. 2 番目のリンク リストを最初のリンク リストにマージし、新しいリンク リストを生成できないようにします。

2. 2 番目のリンク リスト ノードの参照関係は変更できません。つまり、2 番目のリンク リストに影響を与えることはできません。

どうすればいいですか？

この問題には3の分析ポイントがあります:

1. これは、2番目の連結リストの要素を最初の連結リストに挿入する問題です。

2. 挿入されたノードは 2 番目のリンク リストの元のノードではなく、新しいノードである必要があります。そうでない場合は、2 番目のリンク リストに影響します。

3.外側のループは 2 番目のリンク リストの走査を制御し、内側のループは新しいノードの挿入を担当するため、O(m*n) のアルゴリズムになります。

具体的な実装:

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

以上がJavaScript での順序付きリンク リストのマージの詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。