如何在java中以簡單且最佳的方式找到兩個單鍊錶的交集

要以簡單且最佳的方式找到兩個單鍊錶的交集，您可以使用以下方法。關鍵思想是透過調整較長鍊錶的起點來對齊兩個鍊錶的末端，然後同時遍歷兩個鍊錶以找到交點。

步驟：

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 方法計算兩個鍊錶的長度。
   • 對齊起始指標：如果列表的長度不同，則較長列表的指標會前移以與較短列表的指標對齊。
   • 一起遍歷：兩個指針同時移動。它們相符的第一個節點是交集節點。

3. getLength 方法:

   • 計算鍊錶長度的輔助方法。

4. printList 方法:

   • 列印鍊錶節點的實用函數。

5. 主要方法:

   • 建立兩個鍊錶：例如1 -> 3-> 5-> 7-> 9-> 11和2-> 4-> 9-> 11，交叉點從節點 9 開始。
   • 尋找並列印交點：程式將輸出 9 作為交點。

複雜：

• 時間複雜度： ( O(m + n) )，其中 ( m ) 和 ( n ) 是兩個鍊錶的長度。列表最多遍歷兩次。
• 空間複雜度：( O(1) )，因為只使用了一些額外的指標。

此方法簡單且最優，確保您有效率地找到兩個單鍊錶的交點。

以上是如何在java中以簡單且最佳的方式找到兩個單鍊錶的交集的詳細內容。更多資訊請關注PHP中文網其他相關文章！