मान लीजिए हमारे पास एक लिंक्ड लिस्ट है, हमें इस लिस्ट पर इंसर्शन सॉर्ट करना है। उदाहरण के लिए, यदि लिस्ट [9,45,23,71,80,55] जैसी है, तो सॉर्ट की गई लिस्ट [9,23,45,55,71,80] होगी।
हल करने के चरण
- dummy := कुछ रैंडम मान के साथ नया नोड
- node := दी गई लिस्ट
- जब तक node null नहीं है
- newNode = node का next, dummyHead := dummy का next, prevDummyHead := dummy
- जब तक true
- यदि dummyHead मौजूद नहीं है, या dummyHead का मान > node का मान
- node का next := dummyHead
- prevDummyHead का next := node
- लूप तोड़ें
- prevDummyHead := dummyHead, और dummyHead = dummyHead का next
- यदि dummyHead मौजूद नहीं है, या dummyHead का मान > node का मान
- node := nextNode
- dummy का next वापस करें
उदाहरण
#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* insertionSortList(ListNode* a) { ListNode* dummy = new ListNode(-1); ListNode* node = a; ListNode* nextNode; ListNode* dummyHead; ListNode* prevDummyHead; while(node != NULL){ nextNode = node->next; dummyHead = dummy->next; prevDummyHead = dummy; while(1){ if(!dummyHead || dummyHead->val > node->val){ node->next = dummyHead; prevDummyHead->next = node; break; } prevDummyHead = dummyHead; dummyHead = dummyHead->next; } node = nextNode; } return dummy->next; } }; 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, ]