ホームページ > バックエンド開発 > Golang > orted リストをマージする

orted リストをマージする

WBOY
リリース: 2024-07-18 13:26:18
オリジナル
1112 人が閲覧しました

Merge orted lists

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

ソートされた 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 サイトの他の関連記事を参照してください。

ソース:dev.to
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート