C語言單鏈表核心操作大全：考試高頻考點總覽

C語言單鏈表核心操作大全：考試高頻考點總覽

單鏈表是資料結構課程與程式設計面試中的絕對主角。本文整理了一份功能完備的單鏈表函式庫，涵蓋從基礎增刪改查到進階排序、環檢測、約瑟夫環等高頻考點，所有函數均附帶完整實作與詳細註解，適合作為複習速查手冊或專案基礎組件庫。

介面宣告

// linklist.h
#ifndef __LINKLIST_H__
#define __LINKLIST_H__

typedef int DataType;
typedef struct LinkList {
    DataType _data;
    struct LinkList* _next;
} LinkList, *pLinkList;

// 基礎操作
void InitLinkList(pLinkList& pHead);
void PrintLinkList(pLinkList pHead);
int GetListLength(pLinkList pHead);
void DestroyList(pLinkList& pHead);
void PushBack(pLinkList& pHead, DataType Data);
void PopBack(pLinkList& pHead);
void PushFront(pLinkList& pHead, DataType Data);
void BuyNode(pLinkList& pHead, DataType Data);
pLinkList Find(pLinkList pHead, DataType Data);
void Insert(pLinkList pos, DataType Data);
void Remove(pLinkList& pHead, DataType Data);
void RemoveAll(pLinkList& pHead, DataType Data);
void Erase(pLinkList& pHead, pLinkList pos);

// 進階操作（高頻考點）
void BubbleSort(pLinkList pHead);                    // 冒泡排序
int JosephusCircle(pLinkList pHead, int num);        // 約瑟夫環
void QuickSort(pLinkList pHead, pLinkList pEnd);     // 快速排序
void ReverseList(pLinkList& pHead);                  // 鏈表反轉
pLinkList IfCircleList(pLinkList pHead);             // 環檢測
pLinkList CircleListEntrance(pLinkList pHead);       // 環入口

#endif

核心函數實作精選

基礎增刪改查

// 尾插
void PushBack(pLinkList& pHead, DataType Data) {
    pLinkList tmp = pHead;
    if (pHead == NULL) {
        BuyNode(pHead, Data);
    } else {
        while (tmp->_next) tmp = tmp->_next;
        BuyNode(tmp->_next, Data);
    }
}

// 刪除指定值節點（首次出現）
void Remove(pLinkList& pHead, DataType Data) {
    pLinkList del = Find(pHead, Data);
    pLinkList tmp = pHead;
    if (pHead == NULL) return;
    if (pHead == del) {
        pHead = pHead->_next;
        free(tmp);
        return;
    }
    while (tmp->_next) {
        if (tmp->_next == del) {
            tmp->_next = tmp->_next->_next;
            free(del);
            return;
        }
        tmp = tmp->_next;
    }
}

// 反轉鏈表（迭代法，O(1) 空間）
void ReverseList(pLinkList& pHead) {
    pLinkList NewHead = NULL;
    pLinkList tmp = NULL;
    if (!pHead || !pHead->_next) return;
    while (pHead) {
        NewHead = pHead->_next;
        pHead->_next = tmp;
        tmp = pHead;
        pHead = NewHead;
    }
    pHead = tmp;
}

經典演算法題目實作

1. 環檢測與入口尋找（快慢指標法）

// 檢測環，返回相遇節點
pLinkList IfCircleList(pLinkList pHead) {
    pLinkList fast = pHead, slow = pHead;
    assert(pHead);
    while (fast && fast->_next) {
        fast = fast->_next->_next;
        slow = slow->_next;
        if (fast == slow) return fast;
    }
    return NULL;
}

// 尋找環入口
pLinkList CircleListEntrance(pLinkList pHead) {
    pLinkList head = pHead;
    pLinkList meet = IfCircleList(pHead);
    if (!meet) return NULL;
    while (meet != head) {
        meet = meet->_next;
        head = head->_next;
    }
    return meet;
}

2. 約瑟夫環問題

// 假設鏈表已形成環，num=3 表示每數 3 個刪除一個
int JosephusCircle(pLinkList pHead, int num) {
    pLinkList tmp = pHead;
    assert(pHead);
    while (tmp->_next != tmp) {  // 直到只剩一個節點
        pLinkList del = NULL;
        tmp = tmp->_next->_next;  // 移動 num-1 步
        tmp->_data = tmp->_next->_data;
        del = tmp->_next;
        tmp->_next = tmp->_next->_next;
        free(del);
    }
    return tmp->_data;
}

3. 快速排序（鏈表版）

void QuickSort(pLinkList pHead, pLinkList pEnd) {
    if (pHead == NULL || pHead->_next == NULL) return;
    if (pEnd == pHead || pEnd == pHead->_next) return;

    pLinkList cur = pHead->_next;
    pLinkList prev = pHead;
    pLinkList key = pHead;
    DataType tmp;

    while (cur != pEnd) {
        if (cur->_data < key->_data) {
            prev = prev->_next;
            if (cur != prev) {
                tmp = cur->_data;
                cur->_data = prev->_data;
                prev->_data = tmp;
            }
        }
        cur = cur->_next;
    }
    tmp = prev->_data;
    prev->_data = key->_data;
    key->_data = tmp;

    QuickSort(pHead, prev);
    QuickSort(prev->_next, pEnd);
}

測試驗證範例

// 主函數測試
#include <stdio.h>
#include "linklist.h"

void test1() {
    pLinkList pHead = NULL;
    PushFront(pHead, 1);
    PushFront(pHead, 2);
    PushFront(pHead, 3);
    PushFront(pHead, 4);
    PushFront(pHead, 5);
    PrintLinkList(pHead);  // 5 4 3 2 1

    Insert(Find(pHead, 1), 6);  // 1 後插 6
    Erase(pHead, Find(pHead, 2));  // 刪除 2
    PrintLinkList(pHead);  // 5 4 3 6 1

    ReverseList(pHead);
    PrintLinkList(pHead);  // 1 6 3 4 5

    DestroyList(pHead);
    PrintLinkList(pHead);  // 鏈表為空!
}

int main() {
    test1();
    return 0;
}

高頻考點總結表

熟練掌握上述操作與技巧，將能輕鬆應對絕大多數單鏈表相關的筆試與面試題目。建議針對每個考點獨立練習手寫代碼，並針對邊界條件（空表、單節點、頭尾操作）進行充分測試。