İki əlaqəli siyahının kəsişmə nöqtəsini almaq üçün bir funksiya yazın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Amazon DE Şou Məlumat dəsti Goldman Sachs MakeMyTrip MAQ microsoft Qualcomm Snapdeal Viza Zopper
Bağlı siyahıBaxılıb 26

Problem bəyanat

“İki əlaqəli siyahının kəsişmə nöqtəsini almaq üçün bir funksiya yazın” problemi sizə iki əlaqəli siyahının verildiyini bildirir. Ancaq bunlar müstəqil əlaqəli siyahılar deyil. Bunlar bir nöqtədə bağlıdır. İndi bu iki siyahının bu kəsişmə nöqtəsini tapmaq lazımdır.

misal

İki əlaqəli siyahının kəsişmə nöqtəsini almaq üçün bir funksiya yazınPin

1 -> 2
      \
        5 -> 6
      /
3 -> 4
Point of intersection: 5

İzahat: Girişdə göstərilən 1, 2, 5, 6 və 3, 4, 5, 6-dakı iki əlaqəli siyahı var. Hər ikisi də dəyəri 5 olan düyündə birləşdirilir.

Yanaşma

Problemi izah etmək sadədir. İki var əlaqəli siyahılar ancaq bir nöqtədə birləşdirilir və ya bir-birinə bağlıdır. Qoşulma nöqtəsindən əvvəl, hər iki əlaqəli siyahıda fərqli qovşaqlar var və birləşmə nodundan sonra. Onlar bir siyahı ilə təmsil olunur. Beləliklə, problem belə bir düyünü (və ya nöqtəni) necə tapmaqda? Problemə bir çox mümkün cavab / həll yolu ola bilər. Ancaq ən sadə yol əlaqəli siyahıların uzunluğunu tapmaqdır. Hər hansı bir həll asan olduqda, vaxt məhdudiyyətini keçəcək qədər təsirli deyil. Ancaq burada belə deyil. Bu həll səmərəli və sadədir.

Izahat

Bu həll yolunda, əlaqəli iki siyahının uzunluğunu tapacağıq. Və sonra daha uzun əlaqəli siyahının başını irəliyə aparacağıq (lenA - lenB) qovşaqlar. Budur lenAlenB müvafiq olaraq A və B əlaqəli siyahının uzunluğunu göstərir. Bəs niyə bunu etdik?

Ümumi əlaqəli siyahının uzunluğunu düşünək z, daha uzun siyahının uzunluğu x + z və daha qısa əlaqəli siyahıdır y + z. Beləliklə, indiyə qədər köçdük lenA - lenB daha uzun əlaqəli siyahı üzərində. Yəni (x + z - (y + z)) = x - y. Bu, dayandığımız düyün uzunluğuna qədər daha uzun əlaqəli siyahıdan keçdiyimiz deməkdir y daha qısa əlaqəli siyahının başı kimi birləşmə nodundan. Sonra hər iki əlaqəli siyahıda eyni vaxtda hərəkət edirik və hər iki cari düyünün bərabər olub olmadığını yoxlayırıq. Əgər belədirsə, kəsişmə nöqtəmizi tapdıq. Ancaq əlaqəli siyahıların sonuna qədər belə bir nöqtə tapmasaq. Sonra bu onların kəsişmə nöqtəsi olmadığını göstərir.

Beləliklə, iki əlaqəli siyahının kəsişmə nöqtəsini almaq üçün bir funksiya yazırıq.

Kodu

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

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

int length(ListNode *tmp){
    int cnt =  0;
    while(tmp != NULL){
        cnt++;
        tmp = tmp->next;
    }
    return cnt;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = length(headA);
    int lenB = length(headB);
    
    if(lenA > lenB){
        int cnt = lenA - lenB;
        while(cnt--)
            headA = headA->next;
    } else {
        int cnt = lenB - lenA;
        while(cnt--)
            headB = headB->next;
    }
    while(headA != NULL && headB != NULL){
        if(headA == headB)
            return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  ListNode *headB = create(3);
  headB->next = create(4);
  headA->next->next = headB->next->next = create(5);
  headA->next->next->next = headB->next->next->next = create(6);

  cout<<"Intersection at node: ";
  cout<<getIntersectionNode(headA, headB)->data<<endl;
}
Intersection at node: 5

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

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static int length(ListNode tmp){
        int cnt =  0;
        while(tmp != null){
            cnt++;
            tmp = tmp.next;
        }
        return cnt;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);

        if(lenA > lenB){
            int cnt = lenA - lenB;
            while(cnt-- > 0)
                headA = headA.next;
        } else {
            int cnt = lenB - lenA;
            while(cnt-- > 0)
                headB = headB.next;
        }
        while(headA != null && headB != null){
            if(headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;        
    }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    ListNode headB = create(3);
    headB.next = create(4);
    headA.next.next = headB.next.next = create(5);
    headA.next.next.next = headB.next.next.next = create(6);

    System.out.print("Intersection at node: ");
    System.out.print(getIntersectionNode(headA, headB).data);
  }
}
Intersection at node: 5

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), əlaqəli siyahılardakı hər bir qovşaq üzərində tam bir dəfə işlədiyimiz üçün. Bir kəsişmə nöqtəsi varsa, o düyünə çatdıqda onu qaytarırıq. Başqa hər bir qovşaq yalnız bir dəfə keçilir. Bu zaman mürəkkəbliyinin xətti olduğunu sübut edir.

Kosmik Mürəkkəblik

O (1), saxladığımız tək şey bu alqoritmin yalnız sabit yer tutmasına səbəb olan əlaqəli siyahıların uzunluğudur.

Translate »