C++ में लिंक्ड लिस्ट पर इन्सर्शन सॉर्ट (Insertion Sort List)

मान लीजिए हमारे पास एक लिंक्ड लिस्ट है, हमें इस लिस्ट पर इन्सर्शन सॉर्ट करना है। यदि लिस्ट [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
  • node := newNode
• dummy का next वापस करें

उदाहरण

आइए निम्नलिखित कार्यान्वयन को देखें:

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;
    }
};

इनपुट

[9,45,23,71,80,55]

आउटपुट

[9,23,45,55,71,80]