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

Untuk mencari persilangan dua senarai berpaut tunggal dengan cara yang mudah dan optimum, anda boleh menggunakan pendekatan berikut. Idea utama adalah untuk 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 penunjuk ke nod seterusnya (seterusnya).

2. getIntersectionNode Kaedah:

   • 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.
   • Traverse 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. Cara Senarai Cetak:

   • 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 petunjuk 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!