Insertion Sort สำหรับ Linked List ใน C++

ภาพรวมปัญหา

มี Linked List ต้องทำการจัดเรียงด้วยอัลกอริทึม Insertion Sort

ตัวอย่าง: [9,45,23,71,80,55] → [9,23,45,55,71,80]

ขั้นตอนวิธีแก้

1. สร้าง dummy node ด้วยค่าสุ่ม
2. node := หัวของ linked list ที่ให้มา
3. while node ไม่ใช่ null:
   • newNode = next ของ node, dummyHead := next ของ dummy, prevDummyHead := dummy
   • while true:
     • ถ้า dummyHead ไม่มีอยู่ หรือ ค่าของ dummyHead > ค่าของ node:
       • next ของ node := dummyHead
       • next ของ prevDummyHead := node
       • break loop
     • prevDummyHead := dummyHead, dummyHead = next ของ dummyHead
   • node := nextNode
4. return next ของ dummy

ตัวอย่างโค้ด C++

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

Input / Output

Input:  [9,45,23,71,80,55]
Output: [9,23,45,55,71,80]