জাভাতে দুটি লিংকড লিস্টের ইন্টারসেকশন পয়েন্ট খুঁজে বের করা

লিংকড লিস্ট (Linked List) একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডের দুটি ব্লক থাকে: একটি ব্লকে নোডের ভ্যালু বা ডেটা থাকে এবং অন্য ব্লকে নেক্সট ফিল্ডের অ্যাড্রেস থাকে।

ধরুন আমাদের একটি লিংকড লিস্ট আছে যেখানে প্রতিটি নোডে একটি র‍্যান্ডম পয়েন্টার থাকে যা লিস্টের অন্য নোডগুলোর দিকে পয়েন্ট করে। কাজ হল দুটি লিংকড লিস্ট কোন নোডে ইন্টারসেক্ট (intersect) করছে সেটি খুঁজে বের করা। যদি তারা ইন্টারসেক্ট না করে, তবে NULL বা খালি আউটপুট ফেরত দিতে হবে।

উদাহরণ

ইনপুট-১:

আউটপুট:

2

ব্যাখ্যা: যেহেতু দেওয়া লিংকড লিস্ট '২' ভ্যালুযুক্ত নোডে ইন্টারসেক্ট করছে, তাই আউটপুট হিসেবে '২' ফেরত দেওয়া হবে।

ইনপুট-২:

আউটপুট:

NULL

ব্যাখ্যা: যেহেতু কোনো কমন পয়েন্ট নেই, তাই এই কেসে NULL ফেরত দেওয়া হবে।

সমস্যা সমাধানের পদ্ধতি

আমাদের দুটি লিংকড লিস্ট আছে যারা একটি কমন পয়েন্টে ইন্টারসেক্ট করে। ইন্টারসেকশন পয়েন্ট খুঁজে বের করার জন্য আমরা দুটি লিংকড লিস্ট ট্রাভার্স করব যতক্ষণ না তারা একই ভ্যালুকে পয়েন্ট করে। 어느 সময় লিংকড লিস্টের নেক্সট নোডের পয়েন্টার একই হবে। তাই আমরা সেই নির্দিষ্ট নোডের ভ্যালু ফেরত দিব।

• ডেটা এবং নেক্সট নোডের পয়েন্টারসহ দুটি লিংকড লিস্ট নেওয়া হয়।
• commonPoint(listnode* headA, listnode* headB) ফাংশন দুটি লিংকড লিস্টের পয়েন্টার নেয় এবং ইন্টারসেকশন পয়েন্টের ভ্যালু ফেরত দেয়।
• একটি ইন্টিজার ফাংশন যা লিংকড লিস্টের দৈর্ঘ্য বের করে, হেড থেকে দুটি লিংকড লিস্টের দৈর্ঘ্য ফেরত দেয়।
• এখন দুটি লিস্টের হেডে পয়েন্টার তৈরি করা হয় এবং বড় দৈর্ঘ্যের লিস্টটি (length of first list - length of second list) পর্যন্ত ট্রাভার্স করা হয়।
• এখন লিস্ট ট্রাভার্স করা হয় যতক্ষণ না নেক্সট পয়েন্টার সমান পাওয়া যায়।
• দুটি লিস্ট যেখানে ইন্টারসেক্ট করে সেই নির্দিষ্ট নোডের ভ্যালু ফেরত দেওয়া হয়।

উদাহরণ কোড

public class Solution { 
    static listnode headA, headB; 
    
    static class listnode { 
        int data; 
        listnode next; 
        
        listnode(int d) { 
            data = d; 
            next = null; 
        } 
    } 
    
    int count(listnode head) { 
        int c = 0; 
        while (head != null) { 
            c++; 
            head = head.next; 
        } 
        return c; 
    } 
    
    int commonPoint(listnode headA, listnode headB) { 
        listnode p1 = headA; 
        listnode p2 = headB; 
        
        int c1 = count(headA); 
        int c2 = count(headB); 
        
        if (c1 > c2) { 
            for (int i = 0; i < c1 - c2; i++) { 
                if (p1 == null) { 
                    return -1; 
                } 
                p1 = p1.next; 
            } 
        } 
        
        if (c1 < c2) { 
            for (int i = 0; i < c2 - c1; i++) { 
                if (p2 == null) { 
                    return -1; 
                } 
                p2 = p2.next; 
            } 
        } 
        
        while (p1 != null && p2 != null) { 
            if (p1.data == p2.data) { 
                return p1.data; 
            } 
            p1 = p1.next; 
            p2 = p2.next; 
        } 
        return -1; 
    } 
    
    public static void main(String[] args) { 
        Solution list = new Solution(); 
        list.headA = new listnode(5); 
        list.headA.next = new listnode(4); 
        list.headA.next.next = new listnode(9); 
        list.headA.next.next.next = new listnode(7); 
        list.headA.next.next.next.next = new listnode(1); 
        
        list.headB = new listnode(6); 
        list.headB.next = new listnode(7); 
        list.headB.next.next = new listnode(1); 
        
        System.out.println(list.commonPoint(headA, headB)); 
    } 
}

উপরোক্ত কোড রান করলে আউটপুট হবে:

আউটপুট

7

ব্যাখ্যা: দেওয়া লিংকড লিস্টগুলো ৭-এ ইন্টারসেক্ট করছে।