C++-এ লিংকড লিস্টে ইন্সারশন সর্ট

ধরুন একটি লিংকড লিস্ট আছে। আমাদের এই লিস্টে ইন্সারশন সর্ট করতে হবে। যেমন লিস্ট [9,45,23,71,80,55] হলে সর্টেড লিস্ট হবে [9,23,45,55,71,80]।

সমাধানের ধাপসমূহ:

• dummy := কিছু র‍্যান্ডম ভ্যালু দিয়ে নতুন Node তৈরি
• node := দেওয়া লিস্ট
• while node is not null
  • newNode = node-এর next, dummyHead := dummy-এর next, prevDummyHead := dummy
  • while true
    • যদি dummyHead না থাকে অথবা dummyHead-এর ভ্যালু > node-এর ভ্যালু
      • node-এর next := dummyHead
      • prevDummyHead-এর next := node
      • লুপ ব্রেক
    • prevDummyHead := dummyHead, dummyHead = dummyHead-এর next
  • node := nextNode
• 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]