সিঙ্গলি লিঙ্কড লিস্ট দেওয়া। ইনসারশন সর্ট ব্যবহার করে সর্টেড লিস্ট রিটার্ন করুন।
উদাহরণ: [5,3,2,0,-4,7] → [-4,0,2,3,5,7]।
সমাধানের ধাপসমূহ
- ডামি হেড নোড তৈরি করুন।
- মূল লিস্ট ট্রাভার্স করুন, প্রতিটি নোডকে ডামি লিস্টে সঠিক পজিশনে ইনসার্ট করুন।
- ইনসারশন: ডামি লিস্টে লিনিয়ার সার্চ করে বড় মান পাওয়া পর্যন্ত যান, তার আগে ইনসার্ট করুন।
- টাইম কমপ্লেক্সিটি O(n²), স্পেস O(1)।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x):val(x),next(nullptr){}
};
ListNode* make_list(vector<int> v) {
ListNode* head = new ListNode(v[0]);
for (int i = 1; i < v.size(); i++) {
ListNode* p = head;
while (p->next) p = p->next;
p->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode* head) {
cout << "[";
while (head) { cout << head->val << ", "; head = head->next; }
cout << "]" << endl;
}
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode* dummy = new ListNode(-1);
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
ListNode* prev = dummy;
ListNode* node = dummy->next;
while (node && node->val < curr->val) {
prev = node;
node = node->next;
}
curr->next = node;
prev->next = curr;
curr = next;
}
return dummy->next;
}
};
int main() {
vector<int> v = {5,3,2,0,-4,7};
ListNode* head = make_list(v);
Solution ob;
print_list(ob.insertionSortList(head));
}
ইনপুট
{5,3,2,0,-4,7} আউটপুট
[-4, 0, 2, 3, 5, 7, ]
