Masalah
Kerumitan masa: O(N+M) dengan N dan M ialah panjang dua Senarai Pautan yang diberikan.
Cari panjang kedua-dua nod dan dapatkan perbezaan panjang
Pergi ke hadapan dalam senarai terpanjang mengikut perbezaan panjang kedua-dua senarai, dengan ini kedua-dua senarai akan bermula dari panjang yang sama.
kembali apabila nod yang sama ditemui.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = findLength(headA); int lenB = findLength(headB); ListNode A = headA; ListNode B = headB; int diff = Math.abs(lenA-lenB); if(lenA > lenB){ A = travelAhead(A,diff); } else B = travelAhead(B,diff); return findIntegersection(A,B); } public ListNode findIntegersection(ListNode a, ListNode b){ while(a!=null && b!=null){ if(a.equals(b)) return a; a= a.next; b= b.next; } return null; } public ListNode travelAhead(ListNode head, int diff){ while(diff-->0){ head = head.next; } return head; } public int findLength(ListNode head){ int count = 0; while(head!=null){ head = head.next; count++; } return count; } }
Atas ialah kandungan terperinci Persimpangan dua LinkedLists. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!