Барои гирифтани нуқтаи буриши ду Рӯйхати алоқаманд функсия нависед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Акколити Amazon DE Шо Маълумот Голдман Sachs MakeMyTrip MAQ Microsoft Qualcomm Snapdeal Visa Зопер
Рӯйхати алоқаманд

Изҳороти мушкилот

Масъалаи "Функсия нависед, то нуқтаи буриши ду Рӯйхати алоқамандро ба даст оред" мегӯяд, ки ба шумо ду рӯйхати алоқаманд дода шудааст. Аммо онҳо рӯйхатҳои мустақили алоқаманд нестанд. Онҳо дар як лаҳза пайваст карда мешаванд. Акнун шумо бояд ин нуқтаи буриши ин ду рӯйхатро пайдо кунед.

мисол

Барои гирифтани нуқтаи буриши ду Рӯйхати алоқаманд функсия нависед

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

Шарҳ: Дар вуруд ду рӯйхати алоқаманд нишон дода шудааст, ки 1, 2, 5, 6 ва 3, 4, 5, 6. Ҳардуи онҳо дар гиреҳе муттаҳид карда шуданд, ки арзиши он 5 аст. Ҳамин тавр натиҷа 5 мебошад.

усул

Масъалаи тасвир осон аст. Ду ҳастанд рӯйхати алоқаманд аммо онҳо дар ягон лаҳза пайваст карда мешаванд ё бо ҳам алоқаманданд. Пеш аз нуқтаи ҳамроҳшавӣ, ҳарду рӯйхати пайвастшуда гиреҳҳои гуногун доранд ва пас аз гиреҳи ҳамроҳшавӣ. Онҳо бо рӯйхати ягона муаррифӣ шудаанд. Пас, масъала дар он аст, ки чӣ гуна мо чунин гиреҳро (ё нуқтаро) пайдо кунем? Шояд ҷавобҳо / роҳҳои ҳалли мушкилот зиёд бошанд. Аммо роҳи оддитарин дарёфти дарозии рӯйхатҳои алоқаманд аст. Ҳар вақте, ки ҳалли масъала оддӣ аст, он қадар самарабахш нест, ки мӯҳлатро паси сар кунад. Аммо дар ин ҷо чунин нест. Ин ҳалли муассир ва оддӣ аст.

Шарҳ

Дар ин ҳал, мо дарозии ду рӯйхати алоқамандро пайдо мекунем. Ва он гоҳ мо сархати рӯйхати алоқамандро ба (lenA - lenB) гиреҳҳо. Ин ҷо lenA ва lenB мутаносибан дарозии рӯйхати пайвастшудаи А ва В-ро нишон диҳед. Аммо чаро мо ин корро кардем?

Дарозии рӯйхати алоқамандро ба назар гиред z, дарозии рӯйхати дарозтар x + z ва он рӯйхати алоқаманд кӯтоҳтар аст y + z. Ҳамин тавр, то имрӯз, мо кӯчидем lenA - lenB аз болои рӯйхати алоқамандтар. Ин аст (x + z - (y + z)) = x - y. Ин маънои онро дорад, ки мо аз рӯйхати алоқамандтари дарозтар гузаштем, то он даме, ки гиреҳе, ки мо дар он истодаем, дарозӣ дошта бошад y аз гиреҳи пайвастшавӣ ҳамчун сарлавҳаи рӯйхати алоқаманд кӯтоҳтар. Пас мо ҳамзамон дар ҳарду рӯйхати алоқаманд ҳаракат карда, баробар будани ҳарду гиреҳи ҷориро месанҷем. Агар ҳа, мо нуқтаи буриши худро пайдо кардем. Аммо агар мо то охири рӯйхати алоқаманд ягон нуқтае ёбем. Он гоҳ ин нишон медиҳад, ки онҳо нуқтаи буриш надоранд.

Ҳамин тавр, мо вазифаеро барои навиштани нуқтаи буриши ду Рӯйхати пайванд менависем.

рамз

Коди C ++ барои ёфтани чорроҳаи ду рӯйхати алоқаманд

#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

Рамзи Java барои ёфтани чорроҳаи ду рӯйхати алоқаманд

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

Таҳлили мураккабӣ

Мураккабии вақт

O (N), азбаски мо ҳар як гиреҳро дар рӯйхатҳои алоқаманд дақиқ як маротиба аз сар гузаронидаем. Агар нуқтаи буриш мавҷуд бошад, пас вақте ки ба он гиреҳ мерасем, онро бармегардонем. Дигар ҳар як гиреҳ танҳо як маротиба убур мекунад. Ин исбот мекунад, ки мураккабии вақт хатӣ аст.

Мураккабии фазо

О (1), ягона чизе, ки мо захира кардем, дарозии рӯйхатҳои алоқаманд мебошад, ки ин алгоритмро танҳо фазои доимӣ мегирад.