單鏈表排序實戰：從大到小排序成績數據的完整指南

問題背景

在數據結構學習與實際開發中，單鏈表排序是經典題目之一。本文針對「帶頭節點的單鏈表，頭節點數據域為空，長度未知，根據數據域成績從大到小排序」這一具體場景，提供詳細的解題思路與代碼實現。

核心思路：插入排序法

對於單鏈表，最直觀且易於實現的排序算法是插入排序。基本邏輯是：將原鏈表視為「無序區」，建立一個新的「有序區」鏈表（初始為空），依次從無序區取出節點，插入到有序區的適當位置，直到無序區為空。

算法步驟

1. 創建一個新的頭節點 sortedHead，其 next 初始為 NULL，代表有序鏈表。
2. 遍歷原鏈表，使用指針 curr 指向當前待插入節點，next 保存下一個節點防止斷鏈。
3. 在有序鏈表中尋找插入位置：從 sortedHead 開始，找到第一個數據域 小於 待插入節點成績的節點 pre，將待插入節點插在 pre 之後。
4. 重複步驟 2-3，直到原鏈表遍歷完畢。
5. 原頭節點的 next 指向 sortedHead->next，釋放 sortedHead，完成就地排序。

關鍵代碼實現（C 語言）

typedef struct Node {
    int score;          // 成績數據域
    struct Node *next;  // 指針域
} Node;

void SortListDescending(Node *head) {
    if (!head || !head->next) return; // 空表或單節點無需排序

    Node *sortedHead = (Node *)malloc(sizeof(Node));
    sortedHead->next = NULL;          // 有序鏈表初始為空
    Node *curr = head->next;          // 從第一個數據節點開始
    head->next = NULL;                // 斷開原鏈表，避免殘留指針干擾

    while (curr) {
        Node *next = curr->next;      // 保存下一節點
        Node *pre = sortedHead;       // 從有序頭節點開始找位置
        // 找到第一個成績 < 當前節點成績的位置（實現降序）
        while (pre->next && pre->next->score >= curr->score) {
            pre = pre->next;
        }
        // 插入操作
        curr->next = pre->next;
        pre->next = curr;
        curr = next;                  // 處理下一個節點
    }

    // 掛回原頭節點
    head->next = sortedHead->next;
    free(sortedHead);
}

複雜度分析與優化建議

• 時間複雜度：O(n²)，適合數據量較小或基本有序的場景。
• 空間複雜度：O(1)，僅使用常數級額外空間。
• 進階優化：若數據量大，可考慮歸併排序（O(n log n)），利用快慢指針分割鏈表，遞歸排序後合併，更適合單鏈表結構。

常見坑點提醒

• 務必在斷開原鏈表節點前保存 next 指針，否則鏈表將斷裂導致內存洩漏或死循環。
• 頭節點數據域為空，排序邏輯只處理 head->next 之後的數據節點。
• 插入位置查找條件 pre->next->score >= curr->score 保證了穩定性（相同成績節點相對順序不變）並實現降序。

掌握單鏈表排序不僅是考試必考點，更是理解指針操作、內存管理的絕佳練習。建議動手調試上述代碼，觀察指針變化，加深理解。