アルゴリズム: 2つの順序付きリンクリストをマージする

[[414979]]

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

2 つの昇順リンク リストを新しい昇順リンク リストにマージして返します。新しいリンク リストは、指定された 2 つのリンク リストのすべてのノードを連結することによって構築されます。

例：

入力: 1->2->4、1->3->4
出力: 1->1->2->3->4->4

答え：

問題を解決するためのデータ構造を決定する: 単方向リンクリスト

解決策を決定します。リンク リストの先頭から比較を開始します。l1 と l2 は順序付けられ、増加しているため、l1.val と l2.val の小さい方の値が、結合されたリンク リストの最小値になります。2 番目に小さい値は、小さいノードの next.val と大きいノードの val の小さい方の値です。l1 と l2 が両方とも null になるまで、このプロセスを再帰的に繰り返します。

描画の実装: 描画は理解を助ける

境界条件を決定します。再帰的にリンク リストに到達し、それが null の場合、再帰を続行せずに、別のリンク リストの次をポイントします。

コード実装:

関数mergeTwoLists(l1, l2) {
    l1 === nullの場合
l2を返す
    }
    l2 === nullの場合
l1を返す
    }
    l1.val <= l2.val の場合 {
        l1.next = 2つのリストをマージします(l1.next 、 l2)
 l1を返す
    }それ以外{
        l2.next = 2つのリストをマージします(l2.next 、 l1)
 l2を返す
    }
 }

出典: https://github.com/sisterAn/JavaScript-Algorithms