ধরুন আমাদের একটি লিঙ্কযুক্ত তালিকা আছে, আমাদের এই তালিকায় সন্নিবেশ বাছাই করতে হবে। তাই যদি তালিকাটি [9,45,23,71,80,55] এর মত হয় তবে সাজানো তালিকা হল [9,23,45,55,71,80]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ডামি :=কিছু র্যান্ডম মান সহ নতুন নোড
-
নোড :=দেওয়া তালিকা
-
যখন নোড শূন্য নয়,
-
newNode =নোডের পরের, dummyHead :=ডামির পরের, prevDummyHead :=ডামি
-
যদিও সত্য -
-
ডামিহেড উপস্থিত না থাকলে, ডামিহেডের মান> নোডের মান
-
নোডের পরের:=ডামিহেড
-
prevDummyHead এর পরের :=নোড
-
লুপ ভাঙ্গুন
-
-
prevDummyHead :=dymmyHead, এবং dummyHead =ডামি হেডের পাশে
-
-
node :=nextNode
-
- ডামির পরের রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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]