ধরা যাক একটি লিস্ট আছে, আমরা এটিকে O(n log n) সময় এবং কনস্ট্যান্ট স্পেস কমপ্লেক্সিটিতে সর্ট করব। যদি লিস্ট হয় [4,2,1,3], তবে সেটি হবে [1,2,3,4]
সমাধানের ধাপগুলো −
দুটি লিস্টকে সর্টেড ক্রমে মার্জ করার জন্য merge() নামে একটি মেথড সংজ্ঞা করব, যা দুটি লিস্ট l1 এবং l2 নিবে।
সর্ট লিস্ট মেথডটি নিচেরভাবে কাজ করবে −
যদি head null হয় বা head-এর next null হয়, তবে head রিটার্ন করব
slow := head, fast := head, এবং prev = null
যখন fast null নয় এবং fast-এর nextও null নয়
prev := slow
slow := slow-এর next
fast := fast-এর next-এর next
prev-এর next := null
l1 := sortList(head)
l2 := sortList(slow)
merge(l1, l2) রিটার্ন করব
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class ListNode{ public: int val; ListNode *next; ListNode(int data){ val = data; next = NULL; } }; ListNode *make_list(vector<int> v){ ListNode *head = new ListNode(v[0]); for(int i = 1; i<v.size(); i++){ ListNode *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new ListNode(v[i]); } return head; } void print_list(ListNode *head){ ListNode *ptr = head; cout << "["; while(ptr){ cout << ptr->val << ", "; ptr = ptr->next; } cout << "]" << endl; } class Solution { public: ListNode* sortList(ListNode* head) { if(!head || !head->next)return head; ListNode *slow = head, *fast = head, *prev = NULL; while(fast && fast->next){ prev = slow; slow = slow->next; fast = fast->next->next; } prev->next = NULL; ListNode* l1 = sortList(head); ListNode* l2 = sortList(slow); return mergeList(l1,l2); } ListNode* mergeList(ListNode* l1, ListNode* l2){ ListNode* temp = new ListNode(0); ListNode* p =temp; while(l1 && l2){ if(l1->val<=l2->val){ p->next = l1; l1 = l1->next; }else{ p->next = l2; l2 = l2->next; } p = p->next; } if(l1){ p->next = l1; } if(l2){ p->next = l2; } return temp->next; } }; main(){ vector<int> v = {4,2,1,3,5,19,18,6,7}; ListNode *h1 = make_list(v); Solution ob; print_list((ob.sortList(h1))); }
ইনপুট
[4,2,1,3,5,9,8,6,7]
আউটপুট
[1, 2, 3, 4, 5, 6, 7, 18, 19, ]
