Sắp xếp chèn danh sách liên kết trong C++

Sắp xếp danh sách liên kết đơn bằng thuật toán Insertion Sort.

Ví dụ: [9,45,23,71,80,55] → [9,23,45,55,71,80].

Thuật toán giải quyết (Dummy head + Chèn từng nút)

1. Tạo node giả dummy.
2. Duyệt danh sách gốc node:
   • Lưu nextNode = node->next.
   • Tìm vị trí chèn trong danh sách đã sắp xếp (bắt đầu từ dummy->next).
   • Chèn node giữa prevDummyHead và dummyHead.
   • node = nextNode.
3. Trả về dummy->next.

Ví dụ minh họa (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(-1);
        ListNode *node = head;
        while (node) {
            ListNode *nextNode = node->next;
            ListNode *prev = &dummy, *cur = dummy.next;
            while (cur && cur->val < node->val) {
                prev = cur;
                cur = cur->next;
            }
            node->next = cur;
            prev->next = node;
            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));
}

Đầu vào

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

Đầu ra

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