İki Əlaqəli Siyahının kəsişməsi LeetCode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Airbnb Amazon alma Bloomberg ByteDance eBay Facebook Goldman Sachs google Intuit LinkedIn microsoft Morgan Stanley Nutanix Nvidia Kahin PayPal Qualcomm Samsung Spotify Über Yahoo
Redfin tiktokBaxılıb 21

Problem bəyanat

İki Əlaqəli Siyahının kəsişməsi LeetCode Həlli – Bizə iki güclü əlaqəli siyahının başlıqları verilir headA və headB. İki əlaqəli siyahının müəyyən bir nöqtədə kəsişə biləcəyi də verilir. Bizdən onların kəsişdiyi node və ya heç bir kəsişmə yoxdursa, sıfır nöqtəsini qaytarmağımız xahiş olunur.

Nümunələr və izahat

Misal 1:

İki Əlaqəli Siyahının kəsişməsi LeetCode HəlliPin

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Misal 2:

İki Əlaqəli Siyahının kəsişməsi LeetCode HəlliPin

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Misal 3:

İki Əlaqəli Siyahının kəsişməsi LeetCode HəlliPin

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Yanaşma

İdeya çox intuitivdir, biz sadəcə verilmiş əlaqəli siyahıların uzunluqları arasındakı fərqi tapa bilərik və daha uzun siyahının kökünü və ya baş düyününü bu fərqə dəyişə bilərik. Bir kəsişmə ilə qarşılaşana qədər qovşaqları təkrarlamağa davam edin. Əgər qovşaqlardan biri NULL və ya nullptr olarsa, onda heç bir kəsişmə yoxdur, NULL qaytarın, əks halda qovşağı qaytarın.

Kodu

İki əlaqəli siyahının kəsişməsi üçün C++ kodu

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // declaring integers to store the size of the linked lists
        int a=0, b=0;
        // to count the size of the linked list iterate through each node & increment size
        ListNode *currA = headA, *currB = headB;
        while(currA != NULL){
            currA = currA -> next;
            a++;
        }
        while(currB != NULL) {
            currB = currB->next;
            b++;
        }
        
        int k = abs(b-a);
        if ( b > a ) {
            //if the size of B > A, then b becomes b->next till the difference a-b becomes zero
            while(k--) {
                headB = headB -> next;
            }
        }
        else {
            //if the size of B < A, then a becomes a->next till the difference a-b becomes zero
            while(k--) {
                headA = headA -> next;
            }
        }
        
        // check if the headA and headB are equal, if not then move to next pointers of headA and headB
        while(headA != headB && headA->next != NULL && headB->next != NULL) {
            headA = headA -> next;
            headB = headB -> next;
        }
        
        // if one of the list becomes NULL and still no node is found common then return NULL
        if(headA != headB) return NULL;
        
        // if above statement is not true, then return the common node either headA or headB
        return headA;
    }
};

İki əlaqəli siyahının kəsişməsi üçün Java kodu

/**
 * 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 a=0, b=0;
        ListNode currA = headA, currB = headB;
        while(currA != null){
            currA = currA.next;
            a++;
        }
        while(currB != null) {
            currB = currB.next;
            b++;
        }
        int k = Math.abs(b-a);
        if ( b > a ) {
            while(k>0) {
                headB = headB.next;
                k--;
            }
        }
        else {
            while(k>0) {
                headA = headA.next;
                k--;
            }
        }
        
        while(headA != headB && headA.next != null && headB.next != null) {
            headA = headA.next;
            headB = headB.next;
        }
        
        if(headA != headB) return null;
        
        // if above statement is not true, then return the common node either headA or headB
        return headA;
    }
}

İki əlaqəli siyahının kəsişməsi üçün mürəkkəblik təhlili LeetCode Həlli

N, A siyahısının uzunluğu, M isə B siyahısının uzunluğu olsun.

  • Zaman mürəkkəbliyi: O(N + M)
    • Ən pis halda, yəni kəsişmə sonuncu qovşaqda hər bir siyahı O(N+M) vaxtı ilə iki dəfə keçiləcək. Qeyd edək ki, daha uzun siyahı 'k' dəfə keçdikdən sonra və ya siyahılar düzüldükdən sonra deyə bilərik ki, bu alqoritm hər siyahı qovşağından yalnız bir dəfə keçir. Bunun səbəbi budur ki, göstəricilər əvvəlcə hər bir siyahıdan aşağı düşür ki, onlar “sıraya düzülə” və sonra ikinci iterasiyada kəsişmə node axtarılır.
  • Kosmik mürəkkəblik: O (1)
    • Biz heç bir əlavə məlumat strukturu ayırmırıq, ona görə də istifadə olunan əlavə yerin miqdarı daxiletmənin ölçüsü ilə artmır.
Translate »