C++-এ দুটি লিঙ্কড লিস্টের ইন্টারসেকশন পয়েন্ট খুঁজে বের করা

দুটি লিঙ্কড লিস্ট যদি কোনো নোডে মিলিত হয়, তবে সেই ইন্টারসেকশন নোডটি খুঁজে বের করতে হবে। যদি মিলিত না হয়, তবে NULL রিটার্ন।

অ্যালগরিদম

দুটি লিস্টের দৈর্ঘ্য গণনা করুন (len1, len2)।
বড় লিস্টের পয়েন্টারকে |len1-len2| ধাপ এগিয়ে দিন।
এখন দুটি পয়েন্টার একসাথে চলুন। যখন p1 == p2 হয়, সেটিই ইন্টারসেকশন।
টাইম: O(m+n), স্পেস: O(1)

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int d) : data(d), next(nullptr) {}
};

int getLength(ListNode* head) {
    int len = 0;
    while (head) { len++; head = head->next; }
    return len;
}

int findIntersection(ListNode* headA, ListNode* headB) {
    int len1 = getLength(headA), len2 = getLength(headB);
    ListNode *p1 = headA, *p2 = headB;
    
    if (len1 > len2) for (int i=0; i<len1-len2; i++) p1 = p1->next;
    else for (int i=0; i<len2-len1; i++) p2 = p2->next;
    
    while (p1 && p2) {
        if (p1 == p2) return p1->data;
        p1 = p1->next; p2 = p2->next;
    }
    return -1; // NULL
}

int main() {
    // ListA: 5→7→3
    // ListB: 4→9→2→7→3 (7-এ মিলিত)
    ListNode *headA = new ListNode(5);
    headA->next = new ListNode(7);
    headA->next->next = new ListNode(3);
    
    ListNode *headB = new ListNode(4);
    headB->next = new ListNode(9);
    headB->next->next = new ListNode(2);
    headB->next->next->next = headA->next; // 7-এ মিলিত
    
    cout << findIntersection(headA, headB) << endl; // 7
    return 0;
}

C++-এ দুটি লিঙ্কড লিস্টের ইন্টারসেকশন পয়েন্ট খুঁজে বের করা

অ্যালগরিদম

উদাহরণ কোড

আউটপুট