C++ 鏈表插入排序完整實現：結構體定義、創建、排序、銷毀

節點結構與比較函數

struct Student {
    int id;           // 學號 (排序鍵)
    char name[32];
    char gender;      // 'M'/'F'
    int age;
    Student* next;
};

// 比較函數：按學號升序
bool lessThan(const Student* a, const Student* b) {
    return a->id < b->id;
}

創建鏈表 (尾插法，帶虛擬頭節點)

Student* createList(int n) {
    Student* head = new Student(); // 虛擬頭節點
    head->next = nullptr;
    Student* tail = head;
    
    for (int i = 0; i < n; ++i) {
        Student* node = new Student();
        std::cin >> node->id >> node->name >> node->gender >> node->age;
        node->next = nullptr;
        tail->next = node;
        tail = node;
    }
    return head; // 返回虛擬頭節點
}

插入排序核心算法 (就地重組指針)

// 對帶虛擬頭節點的鏈表進行插入排序
void insertionSort(Student* head) {
    if (!head || !head->next || !head->next->next) return; // 0或1個元素
    
    Student* sorted = head->next; // 已排序部分尾節點
    Student* curr = sorted->next; // 待插入節點
    sorted->next = nullptr;       // 切斷，已排序部分初始只有第一個節點
    
    while (curr) {
        Student* next = curr->next; // 保存下一個待處理
        
        // 在已排序部分尋找插入位置
        Student* prev = head;
        while (prev->next && lessThan(prev->next, curr)) {
            prev = prev->next;
        }
        
        // 插入到 prev 之後
        curr->next = prev->next;
        prev->next = curr;
        
        // 更新 sorted 尾節點 (優化：若插在末尾)
        if (prev == sorted) sorted = curr;
        
        curr = next;
    }
    // 重新連接頭節點
    head->next = head->next; // 已經是排序後的頭
}

完整主程式

#include 
#include 

int main() {
    int n = 10;
    std::cout << "輸入 10 位學生: 學號 姓名 性別 年齡\n";
    Student* head = createList(n);
    
    std::cout << "排序前:\n";
    printList(head);
    
    insertionSort(head);
    
    std::cout << "排序後 (按學號升序):\n";
    printList(head);
    
    destroyList(head); // 釋放記憶體
    return 0;
}

void printList(Student* head) {
    for (Student* p = head->next; p; p = p->next) {
        std::cout << p->id << "\t" << p->name << "\t" << p->gender << "\t" << p->age << "\n";
    }
}

void destroyList(Student* head) {
    Student* p = head;
    while (p) {
        Student* next = p->next;
        delete p;
        p = next;
    }
}

關鍵點總結

複雜度分析

• 時間：O(n²) 最壞/平均，O(n) 最好 (已有序)。
• 空間：O(1) 額外空間 (就地排序)。
• 穩定性：**穩定** (相等學號不交換順序)。

避坑指南

• 排序後**頭節點的 `next` 已自動指向新頭** (因插入邏輯從 `head` 開始尋找)，無需額外賦值。
• 若無虛擬頭節點，插入頭部需特判 `if (lessThan(curr, head)) { curr->next = head; head = curr; }` 並返回新頭指針。
• 輸入讀取失敗處理：`if(!(std::cin >> ...)) break;`。