এই সমস্যাতে, আমাদের একটি সর্টেড লিংকড লিস্ট দেওয়া আছে যাতে N সংখ্যক এলিমেন্ট আছে। আমাদের কাজ হল সর্টেড লিংকড লিস্টে মেডিয়ান (Median) বের করা।
সর্টেড লিংকড লিস্ট হল একটি সিম্পল লিংকড লিস্ট যেটির সব এলিমেন্ট নির্দিষ্ট ক্রমে সর্টেড থাকে। উদাহরণ - 4 -> 6 -> 7 -> 9 -> NULL
মেডিয়ান (Median) হল লিংকড লিস্টের মাঝপথের এলিমেন্ট। এটিকে বের করা যায়: যদি N বিজোড় হয়: মেডিয়ান হল (n/2)th এলিমেন্ট
যদি N জোড় হয় - মেডিয়ান হল (n/2)th এলিমেন্ট এবং (n/2 + 1)th এলিমেন্টের গড়।
উদাহরণ দেখি:
ইনপুট: 2 -> 3 -> 4 -> 6 -> 9 -> NULL আউটপুট: 4
সমাধানের পদ্ধতি
একটি সহজ পদ্ধতি হল লিংকড লিস্টের সব এলিমেন্ট কাউন্ট করে ট্রাভার্স করা।
এখন, যদি কাউন্ট বিজোড় হয়, তবে আবার লিংকড লিস্ট ট্রাভার্স করে N/2th এলিমেন্ট পর্যন্ত যাব।
যদি কাউন্ট জোড় হয়, তবে N/2th এবং N/2 + 1 th এলিমেন্ট পর্যন্ত যাব, যোগ করে ২ দিয়ে ভাগ করব।
বিকল্প পদ্ধতি
আরেকটি পদ্ধতি হল টু পয়েন্টার ট্রাভার্সাল ব্যবহার করে লিংকড লিস্ট ট্রাভার্স করা এবং এলিমেন্ট কাউন্ট করা।
এলিমেন্ট কাউন্ট না করে মেডিয়ান বের করার একটি অ্যালগরিদম: দুটি পয়েন্টার pointer1 এবং pointer2, কন্ডিশন অনুযায়ী,
যদি pointer1 NULL না হয়, pointer2 হল মেডিয়ান।
যদি pointer1 NULL হয়, তবে (pointer2-এর প্রিভিয়াস নোড + pointer2->data)/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
