రెండు లింక్డ్ జాబితాల ఖండన పాయింట్ పొందడానికి ఒక ఫంక్షన్ రాయండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అకోలైట్ అమెజాన్ డిఇ షా ఫాక్ట్‌సెట్ గోల్డ్మన్ సాచ్స్ MakeMyTrip మాక్య్ మైక్రోసాఫ్ట్ క్వాల్కమ్ స్నాప్డీల్ వీసా జోపర్
లింక్డ్-జాబితా

సమస్యల నివేదిక

“రెండు లింక్డ్ లిస్టుల ఖండన బిందువు పొందడానికి ఒక ఫంక్షన్ రాయండి” అనే సమస్య మీకు రెండు లింక్డ్ లిస్టులను ఇచ్చిందని పేర్కొంది. కానీ అవి స్వతంత్ర అనుసంధాన జాబితాలు కావు. అవి ఏదో ఒక సమయంలో అనుసంధానించబడి ఉంటాయి. ఇప్పుడు మీరు ఈ రెండు జాబితాల ఖండన బిందువును కనుగొనాలి.

ఉదాహరణ

రెండు లింక్డ్ జాబితాల ఖండన పాయింట్ పొందడానికి ఒక ఫంక్షన్ రాయండి

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 చేరిన నోడ్ నుండి చిన్న లింక్డ్ జాబితా యొక్క తల. అప్పుడు మేము లింక్ చేసిన రెండు జాబితాలలో ఒకేసారి కదులుతాము మరియు ప్రస్తుత నోడ్లు రెండూ సమానంగా ఉన్నాయా అని తనిఖీ చేస్తాము. అలా అయితే, మేము మా ఖండన బిందువును కనుగొన్నాము. లింక్ చేయబడిన జాబితాల ముగింపు వరకు మేము అలాంటి పాయింట్ కనుగొనలేకపోతే. అప్పుడు వారికి ఖండన స్థానం లేదని ఇది సూచిస్తుంది.

కాబట్టి రెండు లింక్డ్ జాబితాల ఖండన బిందువును పొందడానికి మేము ఈ విధంగా ఒక ఫంక్షన్ వ్రాస్తాము.

కోడ్

రెండు లింక్డ్ జాబితాల ఖండనను కనుగొనడానికి సి ++ కోడ్

#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), మేము నిల్వ చేసిన ఏకైక విషయం లింక్ చేయబడిన జాబితాల పొడవు, ఈ అల్గోరిథం స్థిరమైన స్థలాన్ని మాత్రమే తీసుకుంటుంది.