සම්බන්ධිත ලැයිස්තු දෙකක ඡේදනය වීමේ ලක්ෂ්‍යය ලබා ගැනීම සඳහා ශ්‍රිතයක් ලියන්න  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇසොලයිට් ඇමේසන් ඩී ෂෝ ෆැක්ට්සෙට් ගෝල්ඩ්මන් සැක්ස් MakeMyTrip MAQ මයික්රොසොෆ්ට් Qualcomm Snapdeal වීසා සොපර්
සම්බන්ධිත ලැයිස්තුව

ගැටළු ප්රකාශය  

“සම්බන්ධිත ලැයිස්තු දෙකක ඡේදනය වීමේ ලක්ෂ්‍යය ලබා ගැනීම සඳහා ශ්‍රිතයක් ලියන්න” යන ගැටලුවේ සඳහන් වන්නේ ඔබට සම්බන්ධිත ලැයිස්තු දෙකක් ලබා දී ඇති බවයි. නමුත් ඒවා ස්වාධීන සම්බන්ධිත ලැයිස්තු නොවේ. ඒවා යම් අවස්ථාවක සම්බන්ධ වේ. දැන් ඔබට මෙම ලැයිස්තු දෙකේ ඡේදනය වීමේ ස්ථානය සොයාගත යුතුය.

උදාහරණයක්  

සම්බන්ධිත ලැයිස්තු දෙකක ඡේදනය වීමේ ලක්ෂ්‍යය ලබා ගැනීම සඳහා ශ්‍රිතයක් ලියන්න

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

පැහැදිලි කිරීම: ආදානයේ 1, 2, 5, 6 සහ 3, 4, 5, 6 ලෙස සම්බන්ධිත ලැයිස්තු දෙකක් ඇත. මේ දෙකම ඒකාබද්ධ වී ඇත්තේ එහි අගය 5 වන නෝඩයෙනි.

ප්රවේශය  

ගැටළුව විස්තර කිරීමට සරල ය. දෙකක් තිබේ සම්බන්ධිත ලැයිස්තු නමුත් ඒවා යම් අවස්ථාවක දී සම්බන්ධ වී හෝ එකිනෙකට සම්බන්ධ වී ඇත. සම්බන්ධ වීමේ ස්ථානයට පෙර, සම්බන්ධිත ලැයිස්තු දෙකම එකිනෙකට වෙනස් නෝඩ් සහ සම්බන්ධ වීමේ නෝඩයෙන් පසුව ඇත. ඒවා තනි ලැයිස්තුවකින් නිරූපණය කෙරේ. ඉතින්, ගැටලුව වන්නේ අප එවැනි නෝඩයක් (හෝ ලක්ෂ්‍යයක්) සොයා ගන්නේ කෙසේද යන්නයි. ගැටලුවට බොහෝ පිළිතුරු / විසඳුම් තිබිය හැකිය. නමුත් වඩාත්ම සරල ක්‍රමය වන්නේ සම්බන්ධිත ලැයිස්තු වල දිග සොයා ගැනීමයි. විසඳුමක් සරල වන සෑම විටම කාල සීමාව පසු කිරීමට තරම් කාර්යක්ෂම නොවේ. නමුත් මෙහි එය එසේ නොවේ. මෙම විසඳුම කාර්යක්ෂම හා සරල ය.

පැහැදිලි කිරීම

මෙම විසඳුම තුළ, අපි සම්බන්ධිත ලැයිස්තු දෙකේ දිග සොයා ගැනීමට යන්නෙමු. ඉන්පසු අපි දිගු සම්බන්ධිත ලැයිස්තුවේ හිස ඉදිරියට ගෙන යන්නෙමු (ලෙනා - lenB) නෝඩ්. මෙතන ලෙනා සහ 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

සම්බන්ධිත ලැයිස්තු දෙකක ඡේදනය සොයා ගැනීමට ජාවා කේතය

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), අප ගබඩා කර ඇති එකම දෙය නම් මෙම ඇල්ගොරිතමයට නියත ඉඩක් පමණක් ලබා දෙන සම්බන්ධිත ලැයිස්තු වල දිග පමණි.