ಎರಡು ಲಿಂಕ್ಡ್ ಪಟ್ಟಿಗಳ ers ೇದಕ ಬಿಂದುವನ್ನು ಪಡೆಯಲು ಒಂದು ಕಾರ್ಯವನ್ನು ಬರೆಯಿರಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಕೋಲೈಟ್ ಅಮೆಜಾನ್ ಡಿಇ ಶಾ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ MakeMyTrip MAQ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಕ್ವಾಲ್ಕಾಮ್ ಸ್ನ್ಯಾಪ್ಡಿಯಲ್ ವೀಸಾ Opp ೊಪ್ಪರ್
ಲಿಂಕ್ಡ್-ಲಿಸ್ಟ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಎರಡು ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್‌ಗಳ point ೇದಕ ಬಿಂದುವನ್ನು ಪಡೆಯಲು ಒಂದು ಕಾರ್ಯವನ್ನು ಬರೆಯಿರಿ” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ಎರಡು ಲಿಂಕ್ ಪಟ್ಟಿಗಳನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಆದರೆ ಅವು ಸ್ವತಂತ್ರ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಗಳಲ್ಲ. ಅವರು ಕೆಲವು ಹಂತದಲ್ಲಿ ಸಂಪರ್ಕ ಹೊಂದಿದ್ದಾರೆ. ಈಗ ನೀವು ಈ ಎರಡು ಪಟ್ಟಿಗಳ ers ೇದಕವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.

ಉದಾಹರಣೆ

ಎರಡು ಲಿಂಕ್ಡ್ ಪಟ್ಟಿಗಳ ers ೇದಕ ಬಿಂದುವನ್ನು ಪಡೆಯಲು ಒಂದು ಕಾರ್ಯವನ್ನು ಬರೆಯಿರಿ

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

ವಿವರಣೆ: ಇನ್ಪುಟ್ನಲ್ಲಿ 1, 2, 5, 6 ಮತ್ತು 3, 4, 5, 6 ಎಂದು ಎರಡು ಲಿಂಕ್ ಪಟ್ಟಿಗಳನ್ನು ತೋರಿಸಲಾಗಿದೆ. ಇವೆರಡೂ ನೋಡ್ನಲ್ಲಿ ವಿಲೀನಗೊಂಡಿವೆ, ಅದರ ಮೌಲ್ಯ 5 ಆಗಿದೆ. ಹೀಗೆ output ಟ್ಪುಟ್ 5 ಆಗಿದೆ.

ಅಪ್ರೋಚ್

ಸಮಸ್ಯೆಯನ್ನು ವಿವರಿಸಲು ಸರಳವಾಗಿದೆ. ಎರಡು ಇವೆ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಗಳು ಆದರೆ ಅವು ಒಂದು ಹಂತದಲ್ಲಿ ಸೇರಿಕೊಳ್ಳುತ್ತವೆ ಅಥವಾ ಪರಸ್ಪರ ಸಂಬಂಧ ಹೊಂದಿವೆ. ಸೇರುವ ಹಂತದ ಮೊದಲು, ಲಿಂಕ್ ಮಾಡಲಾದ ಎರಡೂ ಪಟ್ಟಿಗಳು ವಿಭಿನ್ನ ನೋಡ್‌ಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಸೇರುವ ನೋಡ್‌ನ ನಂತರ. ಅವುಗಳನ್ನು ಒಂದೇ ಪಟ್ಟಿಯಿಂದ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, ಅಂತಹ ನೋಡ್ ಅನ್ನು ನಾವು ಹೇಗೆ ಕಂಡುಹಿಡಿಯುವುದು (ಅಥವಾ ಪಾಯಿಂಟ್)? ಸಮಸ್ಯೆಗೆ ಅನೇಕ ಸಂಭಾವ್ಯ ಉತ್ತರಗಳು / ಪರಿಹಾರಗಳು ಇರಬಹುದು. ಆದರೆ ಲಿಂಕ್ ಮಾಡಲಾದ ಪಟ್ಟಿಗಳ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಅತ್ಯಂತ ಸರಳ ಮಾರ್ಗವಾಗಿದೆ. ಪರಿಹಾರವು ಸರಳವಾದಾಗ, ಸಮಯದ ಮಿತಿಯನ್ನು ಹಾದುಹೋಗುವಷ್ಟು ಸಮರ್ಥವಾಗಿರುವುದಿಲ್ಲ. ಆದರೆ ಇಲ್ಲಿ ಹಾಗೆ ಆಗುವುದಿಲ್ಲ. ಈ ಪರಿಹಾರವು ಪರಿಣಾಮಕಾರಿ ಮತ್ತು ಸರಳವಾಗಿದೆ.

ವಿವರಣೆ

ಈ ಪರಿಹಾರದಲ್ಲಿ, ನಾವು ಎರಡು ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಗಳ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲಿದ್ದೇವೆ. ತದನಂತರ ನಾವು ಮುಂದೆ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಯ ತಲೆಯನ್ನು ಮುಂದಕ್ಕೆ ಸರಿಸಲು ಹೋಗುತ್ತೇವೆ (lenA - lenB) ನೋಡ್‌ಗಳು. ಇಲ್ಲಿ lenA ಮತ್ತು lenB ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿ ಎ ಮತ್ತು ಬಿ ಯ ಉದ್ದವನ್ನು ಕ್ರಮವಾಗಿ ಸೂಚಿಸಿ. ಆದರೆ ನಾವು ಇದನ್ನು ಏಕೆ ಮಾಡಿದ್ದೇವೆ?

ಸಾಮಾನ್ಯ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಯ ಉದ್ದವು z ಎಂದು ಪರಿಗಣಿಸಿ, ಉದ್ದವಾದ ಪಟ್ಟಿಯ ಉದ್ದ x + z ಮತ್ತು ಕಡಿಮೆ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಯಾಗಿದೆ y + z. ಆದ್ದರಿಂದ ಇಲ್ಲಿಯವರೆಗೆ, ನಾವು ಸ್ಥಳಾಂತರಗೊಂಡಿದ್ದೇವೆ lenA - lenB ಮುಂದೆ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಯ ಮೇಲೆ. ಅದು (x + z - (y + z)) = x - y. ಇದರರ್ಥ ನಾವು ಪ್ರಸ್ತುತ ನಿಂತಿರುವ ನೋಡ್ ಸಹ ಉದ್ದವನ್ನು ಹೊಂದುವವರೆಗೆ ನಾವು ಮುಂದೆ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಯ ಮೇಲೆ ಸರಿಸಿದ್ದೇವೆ y ಸೇರುವ ನೋಡ್‌ನಿಂದ ಕಡಿಮೆ ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಯ ಮುಖ್ಯಸ್ಥರಾಗಿ. ನಂತರ ನಾವು ಲಿಂಕ್ ಮಾಡಲಾದ ಎರಡೂ ಪಟ್ಟಿಗಳಲ್ಲಿ ಏಕಕಾಲದಲ್ಲಿ ಚಲಿಸುತ್ತೇವೆ ಮತ್ತು ಪ್ರಸ್ತುತ ಎರಡೂ ನೋಡ್‌ಗಳು ಸಮಾನವಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಹಾಗಿದ್ದಲ್ಲಿ, ನಮ್ಮ ers ೇದಕ ಬಿಂದುವನ್ನು ನಾವು ಕಂಡುಕೊಂಡಿದ್ದೇವೆ. ಆದರೆ ಲಿಂಕ್ ಮಾಡಲಾದ ಪಟ್ಟಿಗಳ ಕೊನೆಯವರೆಗೂ ನಾವು ಅಂತಹ ಯಾವುದೇ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯದಿದ್ದರೆ. ನಂತರ ಅವರು ers ೇದಕ ಬಿಂದುವನ್ನು ಹೊಂದಿಲ್ಲ ಎಂದು ಇದು ಸೂಚಿಸುತ್ತದೆ.

ಆದ್ದರಿಂದ ಎರಡು ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್‌ಗಳ point ೇದಕ ಬಿಂದುವನ್ನು ಪಡೆಯಲು ನಾವು ಒಂದು ಕಾರ್ಯವನ್ನು ಹೇಗೆ ಬರೆಯುತ್ತೇವೆ.

ಕೋಡ್

ಎರಡು ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಗಳ ection ೇದಕವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#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

ಎರಡು ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಗಳ ection ೇದಕವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಲಿಂಕ್ ಮಾಡಿದ ಪಟ್ಟಿಗಳಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ನೋಡ್‌ಗಳನ್ನು ನಿಖರವಾಗಿ ಒಮ್ಮೆ ಓಡಿಸಿದ್ದೇವೆ. Ers ೇದಕ ಬಿಂದು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ ನಾವು ಆ ನೋಡ್ ತಲುಪಿದಾಗ ಅದನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ. ಇಲ್ಲದಿದ್ದರೆ ಪ್ರತಿ ನೋಡ್ ಒಮ್ಮೆ ಮಾತ್ರ ಹಾದುಹೋಗುತ್ತದೆ. ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ ಎಂದು ಇದು ಸಾಬೀತುಪಡಿಸುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ನಾವು ಸಂಗ್ರಹಿಸಿರುವ ಏಕೈಕ ವಿಷಯವೆಂದರೆ ಲಿಂಕ್ ಮಾಡಲಾದ ಪಟ್ಟಿಗಳ ಉದ್ದವು ಈ ಅಲ್ಗಾರಿದಮ್ ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ಮಾತ್ರ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ.