C語言鏈表排序常見錯誤：記憶體複製導致指針異常

在 C 語言中實現鏈表排序時，初學者常會遇到一個隱蔽的問題：當複製結構體內存時，指針成員也被一併複製，導致多個節點指向同一個下一節點，破壞鏈表結構。這篇文章將深入分析這個經典錯誤，並提供正確的解決思路。

問題現象

如圖所示，開發者嘗試通過複製節點數據來實現排序，但發現排序後鏈表出現環或數據錯亂。

錯誤原因分析

鏈表節點通常包含數據域和指針域（如 next 指針）。當使用 memcpy 或直接結構體賦值（node1 = node2）複製節點時，指針的值（即內存地址）被原樣複製。這意味著：

• 原節點和新節點的 next 指向同一個下一節點
• 修改任一節點的 next 都會影響另一個
• 排序過程中交換節點實際上只是交換了數據，指針關係未更新，導致邏輯錯誤

正確做法

鏈表排序應採用「調整指針」而非「複製數據」的策略：

1. 插入排序：遍歷原鏈表，將每個節點摘下，插入到新有序鏈表的適當位置，只修改 next 指針。
2. 歸併排序：利用遞歸將鏈表拆分、合併，過程中只重組指針，不移動數據。
3. 交換節點指針：若必須交換相鄰節點，需同時修改前驅節點的 next 和當前節點的 next，確保鏈表連續性。

代碼示例：插入排序實現

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* insertionSortList(Node* head) {
    Node dummy = {0, NULL};
    Node* cur = head;
    while (cur) {
        Node* next = cur->next;
        Node* prev = &dummy;
        while (prev->next && prev->next->data < cur->data) {
            prev = prev->next;
        }
        cur->next = prev->next;
        prev->next = cur;
        cur = next;
    }
    return dummy.next;
}

總結

鏈表排序的核心是指針操作，切勿直接複製結構體內存。理解指針與內存的關係，採用調整指針的排序算法，才能寫出正確、高效的鏈表排序代碼。