C++ ব্যবহার করে দ্বিগুণ লিঙ্কযুক্ত তালিকার জন্য সাজান মার্জ করুন।

সমস্যা বিবৃতি

একটি দ্বিগুণ লিঙ্ক তালিকা দেওয়া. মার্জ সর্ট অ্যালগরিদম ব্যবহার করে এটি সাজান

তালিকা:10->20->8-17->5->13->4 সাজানো তালিকা:4->5->8->10->13->17->20

অ্যালগরিদম

<পূর্ব>1. যদি হেড NULL হয় বা তালিকায় শুধুমাত্র একটি উপাদান থাকে তাহলে তালিকা2 রিটার্ন করুন। মূল তালিকাকে 2 ভাগে ভাগ করে দুটি তালিকা তৈরি করুন3। তালিকা 4 এর প্রথম এবং দ্বিতীয় অংশ সাজান। উভয় সাজানো তালিকা একত্রিত করুন

উদাহরণ

#include #include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) namespace ব্যবহার করে std;struct node { int data; struct নোড *পরবর্তী; struct নোড *prev;};নোড *createList(int *arr, int n){নোড *head, *p, *q; p =মাথা =নতুন নোড; head->ডেটা =arr[0]; head->prev =NULL; head->পরবর্তী =NULL; জন্য (int i =1; i ডেটা =arr[i]; q->prev =p; q->পরবর্তী =NULL; p->পরবর্তী =q; p =q; } রিটার্ন হেড;} void displaylist(node *head){ while (head !=NULL) { cout <data <<" "; head =head->পরবর্তী; } cout <data data) { head1->next =mergeSortedLists(head1->next, head2); head1->next->prev =head1; head1->prev =NULL; রিটার্ন হেড 1; } else { head2->next =mergeSortedLists(head1, head2->next); head2->next->prev =head2; head2->prev =NULL; রিটার্ন হেড 2; }} void splitList(node *src, node **fRef, node **bRef){ node *fast; নোড *ধীর; slow =src; দ্রুত =src->পরবর্তী; যখন (দ্রুত!=NULL) { দ্রুত =দ্রুত->পরবর্তী; যদি (দ্রুত!=NULL) { ধীর =ধীর->পরবর্তী; দ্রুত =দ্রুত->পরবর্তী; } } *fRef =src; *bRef =ধীরে->পরবর্তী; ধীরে->পরবর্তী =NULL;}অকার্যকর মার্জসোর্ট(নোড **হেড){নোড *পি =*হেড; নোড *a =NULL; node *b =NULL; যদি (p ==NULL || p->পরবর্তী ==NULL) { ফেরত; } স্প্লিটলিস্ট(p, &a, &b); একত্রিত করুন(&a); মার্জসর্ট(&b); *হেড =মার্জ সাজানো তালিকা(a, b);}int main(){ int arr[] ={10, 20, 8, 17, 5, 13, 4}; নোড *মাথা; head =createList(arr, SIZE(arr)); cout <<"বিন্যস্ত তালিকা:" < আউটপুট
 
 আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
 তৈরি করে বিন্যস্ত তালিকা:10 20 8 17 5 13 4 চূড়ান্ত সাজানো তালিকা:4 5 8 10 13 17 20