Javaで2つのソートされたリンクリストをシンプルかつ最適な方法でマージする

ソートされた 2 つのリンク リストのマージは、効率的に解決できる一般的な問題です。 Java を使用してこれを簡単かつ最適な方法で行う方法を次に示します。

手順:

1. ダミー ノードの作成: マージ プロセスを簡素化するためにダミー ノードを使用します。このノードは、マージされたリストの開始点として機能します。
2. ノードの比較: 両方のリンク リストの現在のノードを比較します。小さい方のノードをマージされたリストにアタッチし、そのリストのポインタを前方に移動します。
3. 残りのノードの処理: 一方のリストが他方よりも先に枯渇した場合、枯渇していないリストの残りのノードをマージされたリストに接続します。
4. マージされたリストを返す: マージされたリストはダミー ノードの隣のノードから始まります。

Javaの実装:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to merge two sorted linked lists
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a dummy node to act as the starting point
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Traverse both lists and compare nodes
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // If one list is exhausted, link the remaining nodes of the other list
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // The merged list starts from the next node of the dummy node
        return dummy.next;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create first sorted linked list: 1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // Create second sorted linked list: 2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        System.out.println("First List:");
        list.printList(l1);

        System.out.println("Second List:");
        list.printList(l2);

        // Merge the two lists
        ListNode mergedList = list.mergeTwoLists(l1, l2);

        System.out.println("Merged List:");
        list.printList(mergedList);
    }
}

説明：

1. ListNode クラス:

   • リンクされたリスト内の各ノードを整数値 (val) と次のノードへのポインター (next) で表します。

2. mergeTwoLists メソッド:

   • ダミー ノード: ダミー ノード (ダミー) は、開始点を提供することでマージ プロセスを簡素化するために使用されます。
   • 比較ループ: 両方のリンク リストを調べて、現在のノードを比較します。小さいノードがマージされたリストに追加され、そのリストの次のノードに移動します。
   • 残りのノード: リストの 1 つが使い果たされた後、もう一方のリストの残りの部分をマージされたリストに直接接続します。
   • Return: 最後に、マージされたリストはダミー ノードの次のノードから始まります。

3. printList メソッド:

   • このユーティリティ関数は、リンク リスト内のすべてのノードを出力して、簡単に視覚化できます。

4. メインメソッド:

   • 2 つの並べ替えられたリンク リストを作成します: たとえば、1 -> 3 -> 5と2 -> 4 -> 6.
   • リストを結合します: 結合されたリストは 1 -> になります。 2 -> 3 -> 4 -> 5 -> 6.
   • リストを印刷します: 結合の前後で効果を確認します。

複雑：

• 時間計算量: ( O(n + m) )、ここで ( n ) と ( m ) は 2 つのリンクされたリストの長さです。両方のリストの各ノードは 1 回だけ処理されます。
• 空間の複雑さ: ( O(1) )、いくつかのポインターを除いて追加の空間は使用されないため。

この方法は、2 つのソートされたリンク リストをマージするのにシンプルかつ最適であり、効率的でクリーンなコードを保証します。

以上がJavaで2つのソートされたリンクリストをシンプルかつ最適な方法でマージするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。