Գրեք մի ֆունկցիա `երկու Կապված ցուցակների խաչմերուկի կետը ստանալու համար


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Amazon ԴԵ Շոուն Փաստեր Goldman Sachs-ը MakeMyTrip- ը MAQ Microsoft Qualcomm Snapdeal Visa Opոպեր
Կապված ցուցակ

Խնդիրի հայտարարություն

«Գրել մի գործառույթ երկու Կապված ցուցակների խաչմերուկի կետը ստանալու համար» խնդիրը նշում է, որ ձեզ տրվում է երկու կապված ցուցակ: Բայց դրանք անկախ կապակցված ցուցակներ չեն: Նրանք ինչ-որ պահի կապված են: Այժմ դուք պետք է գտնեք այս երկու ցուցակների հատման այս կետը:

Օրինակ

Գրեք մի ֆունկցիա `երկու Կապված ցուցակների խաչմերուկի կետը ստանալու համար

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

Բացատրություն. Մուտքում ներկայացված են երկու կապակցված ցուցակներ, որոնք 1, 2, 5, 6 և 3, 4, 5, 6 են: Երկուսն էլ միաձուլվում են այն հանգույցում, որի արժեքը 5 է: Այսպիսով, արդյունքը 5 է:

Մոտեցում

Խնդիրը նկարագրելու համար պարզ է. Կան երկու կապված ցուցակներ բայց դրանք ինչ-որ պահի միանում կամ փոխկապակցված են: Միացման կետից առաջ և՛ կապված ցուցակները ունեն տարբեր հանգույցներ, և՛ միացման հանգույցից հետո: Դրանք ներկայացված են մեկ ցուցակով: Այսպիսով, խնդիրն այն է, թե ինչպես ենք մենք գտնում այդպիսի հանգույց (կամ կետ): Խնդիրին կարող են լինել շատ հնարավոր պատասխաններ / լուծումներ: Բայց ամենապարզ ճանապարհն է գտնել կապված ցուցակների երկարությունները: Ամեն անգամ, երբ լուծումը պարզ է, այն այնքան արդյունավետ չէ, որ ժամանակն անցնի: Բայց այստեղ այդ դեպքը չէ: Այս լուծումը արդյունավետ և պարզ է:

բացատրություն

Այս լուծման մեջ մենք կգտնենք երկու կապված ցուցակների երկարությունները: Եվ հետո մենք տեղափոխելու ենք ավելի երկար կապակցված ցուցակի ղեկավարը մինչևlenA - lenB) հանգույցները: Ահա այստեղ lenA և lenB համապատասխանաբար նշանակում են կապակցված A և B ցուցակների երկարությունը: Բայց ինչու՞ մենք դա արեցինք:

Հաշվի առեք, որ ընդհանուր կապակցված ցուցակի երկարությունը z է, իսկ ավելի երկար ցուցակի երկարությունը `XNUMX 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք ուղիղ մեկ անգամ անցել ենք կապված ցուցակների յուրաքանչյուր հանգույցից: Եթե ​​կա հատման կետ, ապա այդ հանգույցին հասնելուն պես այն հետ ենք վերադարձնում: Այլապես յուրաքանչյուր հանգույց անցնում է միայն մեկ անգամ: Սա ապացուցում է, որ ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

O (1), Միակ բանը, որ մենք պահել ենք, կապված ցուցակների երկարությունն է, ինչը ստիպում է այս ալգորիթմին տևել միայն հաստատուն տարածք: