您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言單向鏈表完整實作：核心操作、排序、環檢測與約瑟夫環

編輯：關於C

資料結構定義

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

核心操作函式清單

函式	功能	時間複雜度
`InitLinkList`	初始化頭節點	O(1)
`PushBack`	尾插	O(n)
`PushFront`	頭插	O(1)
`Insert(pos, val)`	指定節點後插入	O(1)
`Find(val)`	查找值對應節點	O(n)
`Remove(val)`	刪除第一個值節點	O(n)
`RemoveAll(val)`	刪除所有值節點	O(n)
`Erase(pos)`	刪除指定位置節點	O(n) 找前驅
`BubbleSort`	冒泡排序（升序）	O(n²)
`QuickSort`	快速排序	O(n log n) 平均
`ReverseList`	鏈表反轉	O(n)
`IfCircleList`	快慢指標檢測環	O(n)
`CircleListEntrance`	尋找環入口	O(n)
`JosephusCircle`	約瑟夫環問題	O(n*m)

關鍵演算法深度解析

1. 鏈表反轉（三指標法）

void ReverseList(pLinkList *pHead) {
    pLinkList prev = NULL;
    pLinkList curr = *pHead;
    while (curr) {
        pLinkList next = curr->_next; // 保存下一個
        curr->_next = prev;           // 反轉指向
        prev = curr;                  // 移動 prev
        curr = next;                  // 移動 curr
    }
    *pHead = prev; // 新頭節點
}

2. 環檢測與入口尋找（Floyd 判圈算法）

pLinkList IfCircleList(pLinkList head) {
    pLinkList fast = head, slow = head;
    while (fast && fast->_next) {
        fast = fast->_next->_next;
        slow = slow->_next;
        if (fast == slow) return fast; // 相遇點
    }
    return NULL; // 無環
}

pLinkList CircleListEntrance(pLinkList head) {
    pLinkList meet = IfCircleList(head);
    if (!meet) return NULL;
    pLinkList p1 = head, p2 = meet;
    while (p1 != p2) { // 相遇點即入口
        p1 = p1->_next;
        p2 = p2->_next;
    }
    return p1;
}

數學證明：設環前長度 a，環長 b，相遇時 slow 走 a+x，fast 走 a+x+kb。因 fast=2*slow → a+x = kb → a = kb-x。從頭與相遇點同速前進，在入口相遇。

3. 快速排序（單向鏈表版）

void QuickSort(pLinkList head, pLinkList end) {
    if (!head || head == end || head->_next == end) return;
    pLinkList key = head, prev = head, cur = head->_next;
    while (cur != end) {
        if (cur->_data < key->_data) {
            prev = prev->_next;
            if (cur != prev) {
                DataType tmp = cur->_data;
                cur->_data = prev->_data;
                prev->_data = tmp;
            }
        }
        cur = cur->_next;
    }
    // 交換 key 與 prev
    DataType tmp = key->_data;
    key->_data = prev->_data;
    prev->_data = tmp;
    QuickSort(head, prev);
    QuickSort(prev->_next, end);
}

※ 單向鏈表無法高效逆向遍歷，故以資料交換代替節點重組，簡化實作。

4. 約瑟夫環

int JosephusCircle(pLinkList head, int k) {
    pLinkList cur = head;
    while (cur->_next != cur) { // 直到剩一個節點
        // 走 k-1 步到達要刪除節點的前驅
        for (int i = 1; i < k-1; i++) cur = cur->_next;
        pLinkList del = cur->_next;
        cur->_next = del->_next;
        free(del);
        cur = cur->_next; // 從下一個繼續
    }
    int survivor = cur->_data;
    free(cur);
    return survivor;
}

記憶體管理關鍵點

所有 `malloc` 配置的節點必須在刪除/銷毀時 `free`。
`DestroyList` 需逐節點釋放，避免記憶體洩漏。
刪除節點時，務必先保存 `next` 指標，再 `free` 當前節點。

測試主程式範例

int main() {
    pLinkList head = NULL;
    InitLinkList(&head);
    PushBack(&head, 1); PushBack(&head, 2); PushBack(&head, 3);
    PushBack(&head, 4); PushBack(&head, 5);
    PrintLinkList(head); // 1 2 3 4 5

    ReverseList(&head);
    PrintLinkList(head); // 5 4 3 2 1

    // 建立環測試
    // Find(head, 5)->_next = Find(head, 2);
    // printf("Circle: %s\n", IfCircleList(head) ? "Yes" : "No");

    DestroyList(&head);
    return 0;
}