दुई लिked्क गरिएको सूचिको प्रतिच्छेदन बिन्दु प्राप्त गर्न प्रकार्य लेख्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ समग्र अमेजन डे श तथ्य Goldman सैक्स MakeMyTrip MAQ माइक्रोसफ्ट Qualcomm स्नैपडल भिषा Zopper
लिंक्ड-सूची

समस्या वक्तव्य

समस्या "दुई लिked्क भएका सूचका बिच्छेद बिन्दु प्राप्त गर्न प्रकार्य लेख्नुहोस्" बताउँछ कि तपाईंलाई दुई लि linked्क सूचीहरू दिइन्छ। तर तिनीहरू स्वतन्त्र लि linked्क सूचीहरू छैनन्। तिनीहरू कुनै बिन्दुमा जोडिएका छन्। अब तपाईंले यी दुई सूचिको छेदनको यस पोइन्ट पत्ता लगाउन आवश्यक छ।

उदाहरणका

दुई लिked्क गरिएको सूचिको प्रतिच्छेदन बिन्दु प्राप्त गर्न प्रकार्य लेख्नुहोस्

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

स्पष्टीकरण: त्यहाँ दुई लि linked्क गरिएका सूचिहरू इनपुटमा देखाइन्छ जुन १, २,,, and र,,,,,, 1. हो। ती दुबै नोडमा गाभिएका छन् जसको मान 2. छ। यसरी आउटपुट is हो।

दृष्टिकोण

समस्या वर्णन गर्न को लागी सरल छ। त्यहाँ दुई छन् लि .्क गरिएका सूचीहरू तर तिनीहरू सामेल हुन्छन् वा केहि बिन्दुमा आपसमा जोडिएका हुन्छन्। सामिल बिन्दु अघि, दुबै लिंक गरिएको सूचीहरूका बिभिन्न नोडहरू र सामिल हुने नोड पछि। तिनीहरू एकल सूचीद्वारा प्रतिनिधित्व हुन्छन्। त्यसोभए समस्या के छ भने हामी कसरी यस्तो नोड (वा पोइन्ट) फेला पार्दछौं? त्यहाँ धेरै सम्भावित उत्तर / समस्या समाधान हुन सक्छ। तर सब भन्दा साधारण तरीका भनेको लि linked्क गरिएका सूचीहरूको लम्बाई पत्ता लगाउनु हो। जब कुनै समाधान सरल छ, यो समय सीमा पार गर्न पर्याप्त कुशल छैन। तर यहाँ त्यस्तो अवस्था छैन। यो समाधान कुशल र सरल छ।

स्पष्टीकरण

यस समाधानमा, हामी दुई लि linked्क गरिएका सूचिको लम्बाई पत्ता लगाउँदछौं। र त्यसपछि हामी अगाडि लामो लि linked्क गरिएको सूचीको टाउको सार्न लागेका छौं (लेना - lenB) नोडहरू। यहाँ लेनाlenB क्रमशः लि linked्क गरिएको सूची A र B को लम्बाई संकेत गर्नुहोस्। तर हामीले यो किन गर्‍यौं?

सामान्य लि list्क गरिएको सूची z को लम्बाइ विचार गर्नुहोस्, लामो सूचीको लम्बाई हो x + z र छोटो लि linked्क गरिएको सूची त्यो हो y + z। अहिले सम्म, हामी सरेका छौं lenA - lenB लामो लिंक गरिएको सूचीमा। त्यो हो (x + z - (y + z)) = x - y। यसको मतलव हामी लामो लि list्क गरिएको सूचीमा सार्‍यौं नोड सम्म जुन हामी हालसालै उभिरहेका छौं त्यसको लम्बाई पनि छ y जोडिएको नोडबाट छोटो लि linked्क गरिएको सूचीको हेडको रूपमा। त्यसो भए हामी दुबै जोडिएको सूचीहरूमा एकसाथ सर्छौं र यदि दुवै हालको नोडहरू बराबर छ कि छैन जाँच्दछौं। यदि त्यसो हो भने हामीले हाम्रो छेदनबिन्दु भेट्टायौं। तर यदि हामीले लि lists्क गरिएका सूचीहरूको अन्त्यसम्म त्यस्तो कुनै पोइन्ट फेला पारेनौं। त्यसो भए यसले संकेत गर्दछ कि उनीहरूसँग कुनै छेदनबिन्दु छैन।

त्यसोभए हामी दुई लिंक्टेड लिस्टहरूको चौराहा बिन्दु प्राप्त गर्न प्रकार्य लेख्छौं।

कोड

C ++ कोड दुई लि linked्क गरिएको सूचीको छेदनछाड पत्ता लगाउन

#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

जाभा कोड दुई लि linked्क गरिएको सूचीको प्रतिच्छेदन पत्ता लगाउन

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), किनकि हामीले लि lists्क सूचीमा प्रत्येक नोडमा एक पटक ठ्याक्कै चलाएका छौं। यदि त्यहाँ कुनै छेदन बिंदु छ भने हामी जुन नोडमा पुग्छौं हामी यसलाई फर्काउँछौं। अर्को प्रत्येक नोड मात्र एक पटक ट्र्याभर्स गरिएको छ। यसले प्रमाण दिन्छ कि समयको जटिलता रैखिक हो।

ठाउँ जटिलता

O (१), केवल चीज जुन हामीले भण्डार गरेका छौं लि linked्क गरिएको सूचीहरूको लम्बाइ हो जसले यस एल्गोरिथ्मलाई मात्र स्थिर स्थान लिन दिन्छ।