orted リストをマージする

今日は、別のリンク リスト タスクを見ていきます。

ソートされた 2 つのリンク リストをマージする関数を作成します。結果のリストは、2 つのリストのノードを使用してソートされたリストになります。

このために、ここにある前回の投稿の汎用リンク リスト実装を使用します

func mergeSortedLists(ll1 LinkedList[int], ll2 LinkedList[int]) LinkedList[int] {
    result := LinkedList[int]{}

    p1 := ll1.Head
    p2 := ll2.Head
    rp := &Node[int]{} // dummy node as result head
    result.Head = rp
    for p1 != nil && p2 != nil {
        if p1.Data >= p2.Data {
            rp.Next = p2
            p2 = p2.Next
        } else {
            rp.Next = p1
            p1 = p1.Next
        }
        rp = rp.Next
    }
    if p1 != nil {
        rp.Next = p1
    }
    if p2 != nil {
        rp.Next = p2
    }
    result.Head = result.Head.Next
    return result
}

ロジックは非常に簡単です。まず、2 つのリストの先頭とその結果のリストへのポインターを設定します。結果のリストの「先頭」がわからないため、プレースホルダーとしてダミー ノードを作成します (これは後で修正します)。また、結果リスト用の現在のノード rp も作成します。

次に、2 つのリストを繰り返し処理します。各リストには現在のノードがあります。各ステップで、現在の 2 つのノードのうちどちらの値が小さいかを調べ、そのノードを結果リストに追加します。次に、そのリストの現在のノード (小さい方のノード) をリスト内の次のノードに移動します。また、結果の現在のノードを次の場所に移動する必要があります。

私たちのループ ロジックは、リストの 1 つの終わりに到達するまでこれを続けるだけです。この時点で、リストの 1 つについて比較する要素がもうないことがわかります。それらはすでに結果リストに含まれています。したがって、もう一方のリストの残りのノードはすでにソートされていることがわかっているので、単純に結果の最後に置くことができます。

これをどのように変えますか?これを最適化できるでしょうか?コメント欄でお知らせください。

ありがとうございます!

この投稿とこのシリーズのすべての投稿のコードはここにあります

以上がorted リストをマージするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。