ٻن ڳن Linkedيل فهرستن جي چوٽي حاصل ڪرڻ لاءِ هڪ فنڪشن لکو


تڪليف جي سطح آسان
بار بار پڇڻ ۾ قبول ڪريو Amazon ڊي شاه حقيقت جو جائزو Goldman سيچ MakeMyTrip جو آهي ايم Microsoft جي Qualcomm اسپيڊل ويزا زيپر
ڳن -يل فهرست

مسئلي جو بيان

مسئلو ”لنڪ لسٽن جي چونڪ واري پوائنٽ حاصل ڪرڻ لاءِ هڪ فنڪشن لکو” ٻڌائي ٿو ته توهان کي ٻه ڳن listsيل لسٽون ڏنيون ويون آهن. پر اهي آزاد ڳن linkedيل فهرستون نه آهن. اهي ڪنهن جاءِ تي ڳن connectedيل آهن. هاڻي توهان کي هنن ٻن فهرستن جي چوڪسي واري پوائنٽ کي ڳولڻ جي ضرورت آهي.

مثال

ٻن ڳن Linkedيل فهرستن جي چوٽي حاصل ڪرڻ لاءِ هڪ فنڪشن لکو

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

وضاحت: انپٽ ۾ ٻه ڳن listsيل فهرستون ڏيکاريل آهن جيڪي 1 ، 2 ، 5 ، 6 ۽ 3 ، 4 ، 5 ، 6. آهن ، ٻئي ٻئي کي نوڊ تي ضم ڪيو ويو آهي جن جي قيمت 5. اهڙيءَ طرح ، پيداوار 5 آهي.

چرچو

مسئلو بيان ڪرڻ لاءِ آسان آهي. ٻہ آھن ڳن listsيل لسٽون پر اهي ڪنهن وقت ۾ شامل يا هڪٻئي سان جڙيل آهن. شامل ٿيڻ واري نقطي کان اڳ ، ٻنهي ڳن listsيل فهرستن جا مختلف نوڊ آهن ۽ شامل ٿيڻ جو نوڊ بعد. انهن کي هڪ فهرست مان نمائندگي ڪئي وڃي ٿي. تنهنڪري ، مسئلو اهو آهي ته اسان ڪئين نوڊ (يا پوائنٽ) ڳوليندا آهيون؟ شايد ھتي ڪيترائي ممڪن جواب / مسئلا حل آھن. پر سڀ کان وڌيڪ سادو رستو ڳن theيل لسٽن جي ڊيگهه ڳولڻ آهي. جڏهن ته ڪو حل سادو آهي ، وقت جي حد پاس ڪرڻ لاءِ ايترو ڪارائتو ناهي. پر هي معاملو هتي ناهي. اهو حل ڪارائتو ۽ سادو آهي.

وضاحت

انهي حل ۾ ، اسان ٻن ڳن linkedيل فهرستن جي ڊيگهه ڳولڻ وارا آهيون. ۽ اڳتي هلي اسان اڳتي سان ڳن linkedيل ڊگهي لنڪ جي سربراهي طرف وڃڻ کان (لينا - لينب) جوڙ. هتي لينا ۽ لينب ڳن listيل فهرست اي ۽ ب جي ترتيب ترتيب ڏيو. پر اسان اهو ڇو ڪيو؟

عام ڳن listيل لسٽ جي ڊيگهه ز تي غور ڪريو ، ڊگھائي لسٽ جي ڊيگهه آھي x + z ۽ ان نن linkedڙي سان ڳن listيل فهرست آھي يار + ز. تنھنڪري ھاڻي تائين ، اسان منتقل ٿي چڪا آھيون لينا - لينب وڌيڪ ڳن linkedيل فهرست مٿان. اهو آهي (x + z - (y + z)) = x - y. ان جو مطلب آهي ته اسان ڊگهي ڳن listيل فهرست مٿان منتقل ڪيو آهي جيستائين نوڊ جنهن تي اسان هن وقت بيٺا آهيون انهي جي ڊيگهه به آهي y جڙيل ڳنodeيل کان نن linkedڙي نن linkedڙي فهرست جي سربراهي وانگر. ان کان پوءِ اسان ٻنهي ڳن listsيل فهرستن تي هڪٻئي سان هلون ٿا ۽ چيڪ ڪيون ٿا ته موجوده ٻن نوڊس برابر آهن. جي ائين آهي ، اسان کي اسان جو چورنگي وارو نڪتو مليو آهي. پر جيڪڏهن اسان ڳن linkedيل فهرستن جي خاتمي تائين ڪوبه اهڙو نقطو نه ڳولي سگھون. پوءِ اهو ظاهر ڪري ٿو ته انهن وٽ هڪ چوٽي وارو نقطو ناهي.

تنهنڪري اهو اسين ڪئين طريقي سان ٻن ڳن theيل فهرستن جي چوٽي کي حاصل ڪرڻ لاءِ هڪ فنڪشن لکون ٿا.

ڪوڊ

ٻن ڳن listsيل لسٽن جو گورا ڳولهڻ لاءِ 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

جاوا ڪوڊ ٻن ڳن 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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، جئين اسان ڳن linkedيل فهرستن ۾ هر هڪ کي ختم ڪري چڪا آهيون. جيڪڏهن اتي هڪ تحرڪ واري نقطي موجود آهي ته جيئن اسين ان نوڊ تائين پهچي وڃون ٿا ته اسان ان کي موٽايو. ايلس هر نوڊ هڪ ڀيرو گندي آهي. انهي مان اهو ثابت ٿئي ٿو ته وقت جي پيچيدگي ليڪ آهي.

خلائي پيچيدگي

اي (1) ، صرف هڪ ئي شيءَ جيڪا اسان اسٽور ڪئي آهي ڳن linkedيل لسٽن جي ڊيگهه آهي جيڪا هن الگورتھم کي صرف مسلسل جڳهه ٺاهي ڇڏي.