Bagaimana untuk mencari persilangan dua senarai pautan tunggal dengan cara yang mudah dan optimum dalam java

Untuk mencari persilangan dua senarai terpaut tunggal dengan cara yang mudah dan optimum, anda boleh menggunakan pendekatan berikut. Idea utama ialah menjajarkan hujung kedua-dua senarai terpaut dengan melaraskan titik mula senarai yang lebih panjang, dan kemudian melintasi kedua-dua senarai secara serentak untuk mencari titik persilangan.

Langkah-langkah:

1. Kira Panjang: Mula-mula, hitung panjang kedua-dua senarai terpaut.
2. Jajarkan Penunjuk Mula: Jika satu senarai lebih panjang daripada senarai yang lain, majukan penudingnya untuk menjajarkan panjang kedua-dua senarai.
3. Cari Persimpangan: Lintas kedua-dua senarai serentak. Nod pertama tempat mereka bertemu ialah titik persilangan.

Pelaksanaan 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.");
        }
    }
}

Penjelasan:

1. Kelas ListNode:

   • Mewakili setiap nod dalam senarai terpaut dengan nilai (val) dan penuding ke nod seterusnya (seterusnya).

2. Kaedah getIntersectionNode:

   • Kira Panjang: Panjang kedua-dua senarai terpaut dikira menggunakan kaedah getLength.
   • Jajarkan Penunjuk Mula: Jika senarai mempunyai panjang yang berbeza, penuding senarai yang lebih panjang dimajukan untuk diselaraskan dengan penuding senarai yang lebih pendek.
   • Melintasi Bersama: Kedua-dua penunjuk kemudian digerakkan serentak. Nod pertama yang dipadankan ialah nod persilangan.

3. Kaedah getLength:

   • Kaedah pembantu untuk mengira panjang senarai terpaut.

4. Kaedah printList:

   • Fungsi utiliti untuk mencetak nod senarai terpaut.

5. Kaedah utama:

   • Buat dua senarai terpaut: Contohnya, 1 -> 3 -> 5 -> 7 -> 9 -> 11 dan 2 -> 4 -> 9 -> 11, di mana persimpangan bermula pada nod 9.
   • Cari dan cetak persimpangan: Program akan mengeluarkan 9 sebagai titik persimpangan.

Kerumitan:

• Kerumitan Masa: ( O(m + n) ), dengan ( m ) dan ( n ) ialah panjang dua senarai yang dipautkan. Senarai dilalui maksimum dua kali.
• Kerumitan Ruang: ( O(1) ), kerana hanya beberapa penunjuk tambahan digunakan.

Kaedah ini mudah dan optimum, memastikan anda menemui titik persilangan dua senarai yang dipautkan dengan cara yang cekap.

Atas ialah kandungan terperinci Bagaimana untuk mencari persilangan dua senarai pautan tunggal dengan cara yang mudah dan optimum dalam java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!