JavaScript の興味深い質問: リンクされたリストのマージ

マージソートについては誰もが知っているはずです。その基本的な考え方は、最初に分割してからマージするプロセスです。

それでは、単一リンクリストをマージソートするにはどうすればよいでしょうか?

まず、次の疑似コードに示すように、リンク リストを分割するメソッドが必要です:

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

リンク リストの末尾ポインタをパラメータとして受け取り、リンク リストを 2 つに分割します (前半)。そして後半部分。

それでは、この中間分割値をどのように決定するのでしょうか?

高速ポインタと低速ポインタを同時に末尾から開始し、高速ポインタは毎回 2 ステップかかり、低速ポインタは毎回 1 ステップかかります。このとき、速いポインタは確実に最初に終点に到達し、遅いポインタは最初に終点に到達します。この時点では、距離の半分しか移動していません。つまり、遅いポインタはちょうどこの分割位置にあります。

残りは簡単に処理でき、境界で切り取り、設定をnullに設定して、最初の段階は完了です。

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

その後、リンク リストは分割され、分割できない単位ノードになる場合もあります。それらをマージして新しい順序付きリンク リストに組み立てる方法を見つける必要があります。したがって、次のマージ メソッドが必要になります。このようなメソッドを書くには、実際には考慮すべきケースがかなり多くあり、それが私のコードに反映されています。

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

さて、まな板のように、分割メソッドと結合メソッドが書かれました。準備は完了です。あとはお肉を切るだけです。 Main メソッド これは再帰的なプロセスです。

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

上記は、JavaScript に関する興味深い質問の内容です: リンクされたリストのマージソート その他の関連コンテンツについては、PHP 中国語 Web サイト (www.php.cn) に注目してください。