დაწერე ფუნქცია ორი დაკავშირებული სიის გადაკვეთის წერტილის მისაღებად


Რთული ტური Easy
ხშირად ეკითხებიან თანამოსაყრელი Amazon დე შოუ ფაქტები Goldman 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 შესაბამისად მიუთითეთ დაკავშირებული A და B სიის სიგრძე. რატომ გავაკეთეთ ეს?

გაითვალისწინეთ, რომ საერთო მიბმული სიის სიგრძე არის 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), მას შემდეგ, რაც ჩვენ ერთხელ გადავიტანეთ დაკავშირებული სიების თითოეულ კვანძზე. თუ არსებობს გადაკვეთის წერტილი, მაშინ, როდესაც ამ კვანძს მივაღწევთ, მას ვაბრუნებთ. სხვა თითოეული კვანძი მხოლოდ ერთხელ გაივლის. ეს ადასტურებს, რომ დროის სირთულე ხაზოვანია.

სივრცის სირთულე

O (1), ერთადერთი, რაც ჩვენ შევინახეთ, არის დაკავშირებული სიების სიგრძე, რაც ამ ალგორითმს მხოლოდ მუდმივ ადგილს უთმობს.