Insertion Sort List ใน C++: เรียง Linked List ด้วย Insertion Sort

โจทย์

เรียง Linked List แบบ Insertion Sort

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

แนวคิด: Dummy Head + Insert Sorted

สร้าง dummy head สร้าง sorted list ใหม่ ดึงโหนดจาก list เดิมทีละตัว insert เข้า sorted list ที่ตำแหน่งที่ถูกต้อง

ขั้นตอน

1. dummy = new ListNode(-1), node = head
2. while node:
   • nextNode = node->next (เก็บไว้ก่อน)
   • หาตำแหน่ง insert ใน sorted list (เริ่มจาก dummy->next):
     • เดิน prevDummyHead และ dummyHead จน !dummyHead || dummyHead->val > node->val
   • Insert: node->next = dummyHead; prevDummyHead->next = node
   • node = nextNode
3. Return dummy->next

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

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode* p = head;
        while (p->next) p = p->next;
        p->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode* head) {
    cout << "[";
    while (head) {
        cout << head->val << ", ";
        head = head->next;
    }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        ListNode* node = head;
        
        while (node) {
            ListNode* nextNode = node->next;
            ListNode* prevDummyHead = dummy;
            ListNode* dummyHead = dummy->next;
            
            while (true) {
                if (!dummyHead || dummyHead->val > node->val) {
                    node->next = dummyHead;
                    prevDummyHead->next = node;
                    break;
                }
                prevDummyHead = dummyHead;
                dummyHead = dummyHead->next;
            }
            node = nextNode;
        }
        return dummy->next;
    }
};

int main() {
    vector<int> v = {5,3,2,0,-4,7};
    ListNode* head = make_list(v);
    Solution ob;
    print_list(ob.insertionSortList(head)); // [-4, 0, 2, 3, 5, 7]
    return 0;
}

อินพุต / เอาต์พุต

Input: {5,3,2,0,-4,7}

Output: [-4, 0, 2, 3, 5, 7]

ความซับซ้อน

• Time: O(n²) - worst case
• Space: O(1) - inplace (ใช้ dummy node เพียง 1 ตัว)