C 語言單鏈表完整實作：從基礎操作到進階演算法

C 語言單鏈表完整實作指南

單鏈表是資料結構的基石，掌握其操作對理解指標、動態記憶體管理至關重要。本文提供一個功能完整、模組化設計的單鏈表實作，涵蓋基礎增刪查改、進階演算法（逆置、合併、尋找中點/倒數第 k 節點）與測試範例。

資料結構定義

typedef int DataType;

typedef struct SListNode {
    DataType data;
    struct SListNode* next;
} SListNode;

核心 API 介面 (SList.h)

關鍵演算法解析

1. 鏈表逆置 (Reverse)

void Reverse(SListNode*& pHead) {
    SListNode* cur = pHead;
    SListNode* newHead = NULL;
    while (cur) {
        SListNode* tmp = cur;
        cur = cur->next;
        tmp->next = newHead;
        newHead = tmp;
    }
    pHead = newHead;
}

核心思想：逐個摘下節點，插入新鏈表頭部。三指標法（cur, newHead, tmp）清晰易懂。

2. 尋找中間節點 / 倒數第 k 節點

// 中間節點：快指標走兩步，慢指標走一步
SListNode* FindMidNode(SListNode* pHead) {
    SListNode *fast = pHead, *slow = pHead;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 倒數第 k 個：快指標先走 k 步，再一起走
SListNode* FindKNode(SListNode* pHead, int k) {
    SListNode *fast = pHead, *slow = pHead;
    while (fast && k--) fast = fast->next;
    if (k > 0) return NULL;  // k 超過鏈表長度
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

3. 合併兩有序鏈表

SListNode* Merge(SListNode* pHead1, SListNode* pHead2) {
    if (!pHead1) return pHead2;
    if (!pHead2) return pHead1;
    SListNode* merged = NULL;
    if (pHead1->data < pHead2->data) {
        merged = pHead1;
        merged->next = Merge(pHead1->next, pHead2);
    } else {
        merged = pHead2;
        merged->next = Merge(pHead1, pHead2->next);
    }
    return merged;
}

遞迴版本簡潔優雅，但注意棧溢出風險；長鏈表建議用迭代版。

測試驗證

提供四組測試函數：

• Test1：基礎增刪操作驗證
• Test2：查找、插入、刪除指定位置
• Test3：進階功能（中點、倒數第 k、反向列印、逆置）
• Test4：排序與合併有序鏈表

常見錯誤與最佳實踐

1. 記憶體洩漏：DestoryList 必須逐節點 free，並將頭指標設 NULL
2. 野指標：free 後立即將指標設 NULL，或使用封裝的 sh_free
3. 引用 vs 指標：需修改頭指標的函數用 SListNode* &，僅遍歷用 SListNode*
4. 邊界條件：空鏈表、單節點、操作頭尾節點必須單獨測試

完整程式碼結構

SList.h      // 介面宣告
SList.c      // 核心實作
Test.c       // 測試用例
main()       // 選擇性執行測試

建議將 SList.h/.c 編譯為靜態庫，專案中直接連結，實現真正的模組化複用。