Javaでシンプルかつ最適な方法で2つの単一リンクリストの共通部分を見つける方法

単純かつ最適な方法で 2 つの単一リンクされたリストの共通部分を見つけるには、次のアプローチを使用できます。重要なアイデアは、長いリストの開始点を調整して両方のリンクされたリストの終端を揃え、両方のリストを同時に走査して交点を見つけることです。

手順:

1. 長さの計算: まず、両方のリンク リストの長さを計算します。
2. 開始ポインタの位置合わせ: 一方のリストが他方のリストより長い場合は、ポインタを進めて両方のリストの長さを揃えます。
3. 交差点の検索: 両方のリストを同時に調べます。それらが交わる最初のノードが交点です。

Javaの実装:

class ListNode {
    int val;
    ListNode next;

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

public class LinkedList {

    // Function to get the intersection node of two linked lists
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // Calculate the lengths of both linked lists
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);

        // Align the start of both lists
        while (lengthA > lengthB) {
            headA = headA.next;
            lengthA--;
        }

        while (lengthB > lengthA) {
            headB = headB.next;
            lengthB--;
        }

        // Traverse both lists together to find the intersection
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        return headA;  // or headB, they are the same at intersection point
    }

    // Utility function to calculate the length of a linked list
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // 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 two linked lists
        // List A: 1 -> 3 -> 5 -> 7 -> 9 -> 11
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(3);
        headA.next.next = new ListNode(5);
        headA.next.next.next = new ListNode(7);
        headA.next.next.next.next = new ListNode(9);
        headA.next.next.next.next.next = new ListNode(11);

        // List B: 2 -> 4 -> 9 -> 11
        ListNode headB = new ListNode(2);
        headB.next = new ListNode(4);
        headB.next.next = headA.next.next.next.next;  // 9
        headB.next.next.next = headA.next.next.next.next.next;  // 11

        System.out.println("List A:");
        list.printList(headA);

        System.out.println("List B:");
        list.printList(headB);

        // Find intersection
        ListNode intersection = list.getIntersectionNode(headA, headB);

        if (intersection != null) {
            System.out.println("Intersection at node with value: " + intersection.val);
        } else {
            System.out.println("No intersection.");
        }
    }
}

説明：

1. ListNode クラス:

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

2. getIntersectionNode メソッド:

   • 長さの計算: 両方のリンク リストの長さは、getLength メソッドを使用して計算されます。
   • 開始ポインタの整列: リストの長さが異なる場合、長いリストのポインタが進められて、短いリストのポインタと整列します。
   • Traverse Together: 両方のポインターが同時に移動します。それらが一致する最初のノードが交差ノードです。

3. getLength メソッド:

   • リンクされたリストの長さを計算するヘルパー メソッド。

4. printList メソッド:

   • リンクされたリストのノードを出力するユーティリティ関数。

5. メインメソッド:

   • 2 つのリンクされたリストを作成します: たとえば、1 ->; 3 -> 5 -> 7 -> 9 -> 11と2 -> 4 -> 9 -> 11、交差点はノード 9 から始まります。
   • 交点を検索して印刷します: プログラムは交点として 9 を出力します。

複雑：

• 時間計算量: ( O(m + n) )、ここで ( m ) と ( n ) は 2 つのリンクされたリストの長さです。リストは最大 2 回走査されます。
• 空間複雑度: ( O(1) )、追加のポインターがいくつかしか使用されないためです。

この方法はシンプルかつ最適であり、単一リンクされた 2 つのリストの交点を効率的に見つけることができます。

以上がJavaでシンプルかつ最適な方法で2つの単一リンクリストの共通部分を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。