मान लीजिए हमारे पास एक लिंक्ड लिस्ट है, हमें इस लिस्ट में इंसर्शन सॉर्ट करना है। तो अगर सूची [9,45,23,71,80,55] की तरह है, तो क्रमबद्ध सूची [9,23,45,55,71,80] है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
डमी:=कुछ यादृच्छिक मान के साथ नया नोड
-
नोड:=दी गई सूची
-
जबकि नोड शून्य नहीं है,
-
newNode =नोड के आगे, डमीहेड:=डमी के आगे, prevDummyHead:=डमी
-
जबकि सच -
-
यदि डमीहेड मौजूद नहीं है, तो डमीहेड का मूल्य> नोड का मूल्य
-
नोड के आगे:=डमीहेड
-
prevDummyHead के आगे:=नोड
-
लूप तोड़ें
-
-
prevDummyHead :=dymmyHead, और dummyHead =डमी हेड के आगे
-
-
नोड:=अगला नोड
-
- डमी के आगे वापसी
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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;
//cout << prevDummyHead->val << " " << node->val << endl;
break;
}
}
prevDummyHead = dummyHead;
dummyHead = dummyHead->next;
}
node = nextNode;
}
return dummy->next;
} इनपुट
[9,45,23,71,80,55]
आउटपुट
[9,23,45,55,71,80]