Java で順序付きリンク リストをマージする方法

質問

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

例 1:

入力: l1 = [1,2,4]、l2 = [1,3,4]
出力: [1,1,2,3,4,4]

例 2:

8e99a69fbe029cd4e2b854e244eab143入力:128dba7a3a77be0113eb0bea6ea0a5d0l1 = [], l2 = []
8e99a69fbe029cd4e2b854e244eab143出力: 128dba7a3a77be0113eb0bea6ea0a5d0[]

例 3:

入力: l1 = [] , l2 = [0]
出力: [0]

アイデア

バージョン 1

• 空のリンク リストを作成する nList

• 両方のリンク リスト (l1、l2) が空ではない場合、2 つのリンク リストの最初の要素の値を比較し、最小のものを取得して追加します。新しいリンク リスト その後、小さなリンク リストの先頭ポインタは次のビットを指し、nList のポインタも次のビットを指します

• 両方のリンク リストがまだ空でない場合、ループを続けます

• 2 つのリンク リストの 1 つが空の場合は、空ではないリンク リストを nList

• ## の後ろに接続します。 #最後に、新しいリンク リストの先頭として nList の次のノードを返します。 ノード

バージョン 2

• まず、2 つのリンク リストが次のリンク リストであるかどうかを確認します。空の場合は、空のリンク リストを直接返します。空でない場合は、下に進みます。

• l1 と l2 のどちらのヘッド ノードが小さいかを判断し、このノードをヘッド ノードとして保存すると、後続のノードが接続されます。このノードで一度に上記を実行します。

• 次のアイデアはバージョン 1 と同じです

答え

バージョン 1

新しいノードを作成し、元のノードを置き換えます。リンク リストは新しいリンク リストに転送されます

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode   = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        all.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        all = all.next;
    }
    all.next = list1 != null ? list1 : list2;
    return head.next;
}

バージョン 2

統合のために元のリンク リストから 1 つを選択し、新しいメモリには適用されません

りー

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