दोन दुवा साधलेल्या सूच्यांचा छेदनबिंदू मिळविण्यासाठी कार्य लिहा


अडचण पातळी सोपे
वारंवार विचारले एकत्रित ऍमेझॉन डीई शॉ फॅक्टसेट गोल्डमन Sachs मेकमायट्रिप एमक्यू मायक्रोसॉफ्ट Qualcomm Snapdeal व्हिसा झोपर
दुवा साधलेली यादी

समस्या विधान

“दोन लिंक्ड याद्याचा छेदनबिंदू मिळविण्यासाठी एखादा फंक्शन लिहा” ही समस्या सांगते की आपल्याला दोन लिंक्ड याद्या दिल्या आहेत. परंतु त्या स्वतंत्र लिंक केलेल्या याद्या नाहीत. ते कधीतरी जोडलेले असतात. आता आपल्याला या दोन याद्यांमधील छेदनबिंदू शोधण्याची आवश्यकता आहे.

उदाहरण

दोन दुवा साधलेल्या सूच्यांचा छेदनबिंदू मिळविण्यासाठी कार्य लिहा

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

स्पष्टीकरणः इनपुटमध्ये दोन जोडलेल्या याद्या दर्शविल्या आहेत ज्या १, २,,, and आणि,,,, Both, of आहेत. त्या दोन्ही नोडमध्ये विलीन केल्या आहेत ज्याचे मूल्य is आहे. अशा प्रकारे आउटपुट is आहे.

दृष्टीकोन

समस्या वर्णन करणे सोपे आहे. तेथे दोन आहेत दुवा साधलेल्या याद्या परंतु ते एखाद्या वेळी सामील झाले आहेत किंवा एकमेकांशी जोडलेले आहेत. सामील होण्यापूर्वी, या दुवा साधलेल्या याद्यांमध्ये वेगवेगळे नोड आणि जॉइनिंग नोड असतात. ते एकाच यादीद्वारे प्रतिनिधित्व केले जातात. तर, समस्या अशी आहे की आम्हाला असे नोड कसे शोधायचे (किंवा बिंदू)? समस्येची अनेक उत्तरे / निराकरणे असू शकतात. परंतु सर्वात सोपा मार्ग म्हणजे जोडलेल्या याद्याची लांबी शोधणे. जेव्हा जेव्हा एखादा सोल्युशन सोपा असतो तेव्हा वेळेची मर्यादा पार करणे पुरेसे कार्यक्षम नसते. पण इथे असे नाही. हे समाधान कार्यक्षम आणि सोपे आहे.

स्पष्टीकरण

या सोल्यूशनमध्ये आम्ही दोन लिंक्ड याद्याची लांबी शोधणार आहोत. आणि नंतर आम्ही यापुढे जोडलेल्या यादीचे डोके पुढे हलवू (लेना - lenB) नोड्स येथे लेना आणि lenB अनुक्रमे जोडलेली यादी अ आणि ब ची लांबी दर्शवा. पण आम्ही हे का केले?

सामान्य दुवा साधलेल्या सूचीची लांबी z असा विचार करा, लांब यादीची लांबी x + z आणि ती छोटी लिंकची यादी आहे y + z. म्हणून आतापर्यंत आम्ही हललो आहोत lenA - lenB यापुढे जोडलेल्या यादीवर. ते आहे (x + z - (y + z)) = x - y. याचा अर्थ असा आहे की आपण सध्या ज्या नोडची लांबी घेत आहोत त्याची लांबी होईपर्यंत आम्ही यापुढे जोडलेल्या यादीवर जात आहोत y जॉइनिंग नोड वरून लहान दुवा साधलेल्या सूचीच्या शीर्षकाप्रमाणे. मग आम्ही दोन्ही दुवा साधलेल्या याद्यांवर एकाच वेळी सरकलो व दोन्ही नोड्स समान आहेत का ते तपासू. तसे असल्यास आम्हाला आपला छेदनबिंदू सापडला आहे. परंतु दुवा साधलेल्या सूचीच्या समाप्तीपर्यंत आम्हाला असा कोणताही बिंदू सापडत नाही. मग हे दर्शविते की त्यांच्याकडे छेदनबिंदू नाही.

अशा प्रकारे आपण दोन लिंक्ड याद्याचे छेदनबिंदू मिळविण्यासाठी फंक्शन लिहू.

कोड

दोन दुवा साधलेल्या सूचीचे छेदनबिंदू शोधण्यासाठी सी ++ कोड

#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

दोन दुवा साधलेल्या सूचीचे छेदनबिंदू शोधण्यासाठी जावा कोड

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), आम्ही लिंक केलेल्या यादीतील प्रत्येक नोडवर एकदाच चाललो आहोत. जर एखादा छेदनबिंदू अस्तित्वात असेल तर आपण त्या नोडवर पोहोचताच ते परत करू. अन्यथा प्रत्येक नोड फक्त एकदाच ट्रान्सव्हर केला जातो. हे सिद्ध करते की वेळेची जटिलता रेषात्मक आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (1), आम्ही संग्रहित केलेली एकमेव गोष्ट म्हणजे दुवा साधलेल्या सूचीची लांबी जे या अल्गोरिदमला फक्त निरंतर जागा घेते.