একটি লিঙ্ক করা তালিকা হল একটি রৈখিক ডেটা কাঠামো যেখানে প্রতিটি নোডে দুটি ব্লক থাকে যেমন একটি ব্লকে নোডের মান বা ডেটা থাকে এবং অন্য ব্লকে পরবর্তী ক্ষেত্রের ঠিকানা থাকে৷
আসুন ধরে নিই যে আমাদের একটি লিঙ্কযুক্ত তালিকা রয়েছে যাতে প্রতিটি নোডে একটি র্যান্ডম পয়েন্টার থাকে যা তালিকার অন্যান্য নোডের দিকে নির্দেশ করে। কাজটি হল নোডটি খুঁজে বের করা যেখানে দুটি লিঙ্কযুক্ত তালিকা একে অপরকে ছেদ করে। যদি তারা ছেদ না করে, তাহলে আউটপুট হিসাবে NULL বা খালি ফেরত দিন।
উদাহরণস্বরূপ
ইনপুট-1:
আউটপুট:
2
ব্যাখ্যা: যেহেতু প্রদত্ত লিঙ্কযুক্ত তালিকাটি নোডকে '2' মানের সাথে ছেদ করে, তাই আমরা আউটপুট হিসাবে মান '2' ফিরিয়ে দেব।
ইনপুট-2:
আউটপুট:
NULL
ব্যাখ্যা: যেহেতু কোন সাধারণ পয়েন্ট নেই, আমরা এই ক্ষেত্রে NULL ফেরত দেব।
এই সমস্যা সমাধানের পদ্ধতি
আমাদের কাছে একটি সাধারণ বিন্দুর সাথে দুটি লিঙ্কযুক্ত তালিকা রয়েছে যেখানে তারা একে অপরকে ছেদ করে। ছেদ বিন্দু খুঁজে পেতে, আমরা উভয় লিঙ্ক তালিকা অতিক্রম করব যতক্ষণ না আমরা দেখতে পাই যে তারা সমানভাবে একই মান নির্দেশ করছে। কিছু সময়ে, লিঙ্ক করা তালিকার পরবর্তী নোডের পয়েন্টার একই হবে। এইভাবে আমরা সেই পয়েন্টের মান ফেরত দেব।
- ডাটা সহ দুটি লিঙ্ক করা তালিকা নিন এবং পরবর্তী নোডে পয়েন্টার করুন।
- একটি ফাংশন commonPoint(listnode*headA, listnode*headB) যথাক্রমে লিঙ্ক করা তালিকার দুটি পয়েন্টার নেয় এবং লিঙ্ক করা তালিকার সাধারণ বা ছেদ বিন্দুর মান প্রদান করে।
- একটি পূর্ণসংখ্যা ফাংশন যা লিঙ্ক করা তালিকার দৈর্ঘ্য খুঁজে বের করে তা তালিকার প্রধান থেকে উভয় লিঙ্ক করা তালিকার দৈর্ঘ্য ফিরিয়ে দেবে।
- এখন উভয় তালিকার মাথায় একটি পয়েন্টার তৈরি করুন এবং তালিকাটি অতিক্রম করুন যেটি তার দৈর্ঘ্যে বড় (প্রথম তালিকার দৈর্ঘ্য - দ্বিতীয় তালিকার দৈর্ঘ্য)।
- এখন তালিকাটি অতিক্রম করুন যতক্ষণ না আমরা পরবর্তী পয়েন্টারটি সমান না পাই।
- সেই নির্দিষ্ট নোডের মান ফেরত দিন যেখানে উভয় তালিকা ছেদ করে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class listnode {
public:
int data;
listnode * next;
};
// Find the length of the linked list
int count(listnode * head) {
int count = 0;
while (head != NULL) {
count++;
head = head -> next;
}
return count;
}
//Function to get the common point of two linked list
int commonPoint(listnode * headA, listnode * headB) {
int len1 = count(headA);
int len2 = count(headB);
listnode * p1 = headA;
listnode * p2 = headB;
if (len1 > len2) {
for (int i = 0; i < len1 - len2; ++i) {
p1 = p1 -> next;
}
}
if (len1 < len2) {
for (int i = 0; i < len2 - len1; ++i) {
p2 = p2 -> next;
}
}
while (p1 != NULL and p2 != NULL) {
if (p1 == p2) {
return p1 -> data;
}
p1 = p1 -> next;
p2 = p2 -> next;
}
return -1;
}
int main() {
listnode * head;
listnode * headA = new listnode();
headA -> data = 5;
listnode * headB = new listnode();
headB -> data = 4;
head = new listnode();
head -> data = 9;
headB -> next = head;
head = new listnode();
head -> data = 2;
headB -> next -> next = head;
head = new listnode();
head -> data = 7;
headA -> next = head;
headB -> next -> next -> next = head;
head = new listnode();
head -> data = 3;
headA -> next -> next = head;
headA -> next -> next -> next = NULL;
cout << commonPoint(headA, headB) << endl;
} উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
আউটপুট
7
ব্যাখ্যা: প্রদত্ত লিঙ্কযুক্ত তালিকাগুলি '7' এ একত্রিত হচ্ছে৷
৷
