數據結構與算法系列（1）：C++ 封裝單鏈表完整實現

概述

本文展示一個完整的 C++ 單鏈表類 LinkList，封裝了創建、查詢、插入、刪除、逆置、環檢測、排序、合並等核心操作，採用快速排序實現升序排列。

類設計

struct node { int data; node* next; };

class LinkList {
public:
    LinkList(int N = 0);           // 構造函數，可選初始長度
    void CreateList(int n);        // 根據輸入創建鏈表
    int GetLength();               // 獲取元素個數
    void PrintList();              // 打印所有元素
    int SearchNode(int data);      // 查找元素位置（1-based），不存在返回 0
    bool InsertNode(int pos, int data); // 在 pos 位置後插入
    bool DeleteNode(int pos);      // 刪除 pos 位置後的節點
    void Reverse();                // 鏈表逆置
    bool IsLoop();                 // 判斷是否有環（快慢指針）
    void SelfASOrder();            // 升序排序（快速排序）
    void ASCMerge(LinkList& L);    // 升序合並另一鏈表
    void DESCMerge(LinkList& L);   // 降序合並（升序後逆置）
private:
    void QuikSort(node* start, node* end); // 快速排序遞歸實現
    node* head; int len;
};

核心算法實現要點

快速排序於鏈表

以中間節點為基準，將鏈表分為兩段遞歸排序。注意鏈表無隨機訪問，需通過指針移動尋找中點與分區。

環檢測

快慢指針法：slow 每次走一步，fast 走兩步，若相遇則有環。

合並有序鏈表

先對兩表分別排序，再用雙指針歸併；降序合並只需在升序合並後整體逆置。

主程序演示

int main() {
    LinkList L(10);
    cout << "Input the L1 List:" << endl;
    // ... 讀取、查找、插入、刪除、逆置、環檢測、排序、合並演示
    return 0;
}

常見錯誤與優化提示

• GetLength() 重複遍歷，建議維護 len 成員實時更新。
• InsertNode/DeleteNode 中 delete p; delete q; 在指針置空後調用屬於未定義行為，應先 delete 再置空，或使用智能指針。
• 快速排序對鏈表非最優，歸併排序更適合（O(n log n) 且穩定）。
• 缺少拷貝構造函數與賦值運算符，淺拷貝會導致雙重釋放。

總結

代碼完整演示了單鏈表主要操作，適合教學與面試準備。生產環境建議使用 std::list 或實現 Rule of Five、迭代器、異常安全的現代 C++ 容器。