এই সমস্যায়, আমাদের N উপাদানগুলির সমন্বয়ে একটি সাজানো লিঙ্কযুক্ত তালিকা দেওয়া হয়েছে। আমাদের কাজ হল একটি বাছাই করা লিঙ্কযুক্ত তালিকায় মিডিয়ান খোঁজা .
বাছাই করা লিঙ্কযুক্ত তালিকা একটি সহজ লিঙ্কযুক্ত তালিকা যাতে সমস্ত উপাদান একটি নির্দিষ্ট ক্রমে সাজানো হয়। উদাহরণ − 4 -> 6 -> 7 -> 9 -> NULL
মাঝারি লিঙ্ক করা তালিকার মধ্যম উপাদান। এটি পাওয়া যেতে পারে যেন N বিজোড় :মধ্যমা হল (n/2) th উপাদান
যদি N জোড় −s মধ্যমা হয় (n/2) th এর গড় উপাদান এবং (n/2 + 1) th উপাদান।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input: 2 -> 3 -> 4 -> 6 -> 9 -> NULL Output: 4
সমাধান পদ্ধতি
সমস্যাটির একটি সহজ সমাধান হল লিঙ্ক করা তালিকার সমস্ত উপাদানগুলিকে অতিক্রম করে গণনা করা৷
এখন, যদি গণনা বিজোড় হয়, তাহলে আমরা আবার লিঙ্ক করা তালিকার N/2 তম উপাদান পর্যন্ত অতিক্রম করব।
যদি গণনা সমান হয়, আমরা N/2th উপাদান এবং N/2 + 1 ম উপাদান পর্যন্ত অতিক্রম করব, তাদের যোগ করব এবং 2 দ্বারা ভাগ করব।
বিকল্প পদ্ধতি
সমস্যা সমাধানের আরেকটি পন্থা হল দুটি পয়েন্টার ট্রাভার্সাল ব্যবহার করে লিঙ্ক করা তালিকাকে অতিক্রম করা এবং লিঙ্ক করা তালিকার উপাদানের গণনা খুঁজে বের করা।
উপাদানের সংখ্যা গণনা না করেই মধ্যক খুঁজে বের করার জন্য এখানে একটি অ্যালগরিদম রয়েছে। তাদের দুটি পয়েন্টার পয়েন্টার 1 এবং পয়েন্টার 2, শর্তের উপর ভিত্তি করে, আমাদের থাকতে পারে,
পয়েন্টার 1 শূন্য না হলে, পয়েন্টার 2 হল মধ্যমা৷
৷পয়েন্টার 1 যদি NULL হয়, তাহলে (পয়েন্টার2 + পয়েন্টার2 -> ডেটা)/2-এর নোডের আগের।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void findMedianValue(Node* head){
Node* ptr1 = head;
Node* ptr2 = head;
Node* prev = head;
if (head != NULL) {
while (ptr2 != NULL && ptr2->next != NULL) {
ptr2 = ptr2->next->next;
prev = ptr1;
ptr1 = ptr1->next;
}
if (ptr2 != NULL)
cout<<ptr1->data;
else
cout<<float(ptr1->data + prev->data) / 2;
}
}
void pushVal(struct Node** head_ref, int new_data){
Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main(){
struct Node* head = NULL;
pushVal(&head, 3);
pushVal(&head, 5);
pushVal(&head, 6);
pushVal(&head, 8);
pushVal(&head, 9);
pushVal(&head, 11);
cout<<"The median of the linked list is ";
findMedianValue(head);
return 0;
} আউটপুট
The median of the linked list is 7
