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

單向鏈表創建與逆轉完整實現指南（C語言版）

編輯：關於C

前言

單向鏈表是數據結構中的基礎結構，動態內存分配、指針操作是其核心。本文提供一個完整的 C 語言實現，涵蓋鏈表的創建、遍歷輸出、逆轉三大核心操作，並附帶詳細代碼註解與邏輯解析。

一、數據結構定義

typedef struct Node {
    int data;           // 數據域
    struct Node *next;  // 指針域，指向下一個節點
} ListNode;

使用 typedef 簡化類型名稱，struct Node *next 實現自我引用。

二、鏈表創建：尾插法

ListNode* createList() {
    ListNode *head = NULL, *tail = NULL;
    int val;
    printf("請輸入整數（以 0 結束）：");
    while (scanf("%d", &val) == 1 && val != 0) {
        ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
        if (!newNode) { perror("內存分配失敗"); exit(EXIT_FAILURE); }
        newNode->data = val;
        newNode->next = NULL;
        if (!head) head = tail = newNode;  // 首節點
        else { tail->next = newNode; tail = newNode; }  // 尾插
    }
    return head;
}

關鍵點：

雙指針 head/tail 維護首尾，實現 O(1) 尾插。
輸入 0 作為結束標記，不存入鏈表。
必須檢查 malloc 返回值，防止內存耗盡崩潰。

三、鏈表遍歷輸出

void printList(ListNode *head) {
    while (head) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\\n");
}

以指針遍歷至 NULL，時間複雜度 O(n)，空間 O(1)。

四、鏈表逆轉：三指針迭代法

ListNode* reverseList(ListNode *head) {
    ListNode *prev = NULL, *curr = head, *next = NULL;
    while (curr) {
        next = curr->next;  // 暫存後繼節點
        curr->next = prev;  // 反轉指針
        prev = curr;        // prev 後移
        curr = next;        // curr 後移
    }
    return prev;  // 新頭節點
}

圖解過程（以 1→2→3→NULL 為例）：

初始: prev=NULL, curr=1, next=2
步驟1: 1→NULL, prev=1, curr=2, next=3
步驟2: 2→1→NULL, prev=2, curr=3, next=NULL
步驟3: 3→2→1→NULL, prev=3, curr=NULL
返回 prev=3 作為新頭

複雜度：時間 O(n)，空間 O(1)。遞歸版雖簡潔但棧空間 O(n)，大數據量易棧溢出。

五、完整可運行程式

#include 
#include 

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

ListNode* createList() { /* 上述創建代碼 */ }
void printList(ListNode *head) { /* 上述輸出代碼 */ }
ListNode* reverseList(ListNode *head) { /* 上述逆轉代碼 */ }

void freeList(ListNode *head) {  // 釋放內存
    while (head) {
        ListNode *tmp = head;
        head = head->next;
        free(tmp);
    }
}

int main() {
    ListNode *list = createList();
    printf("原鏈表："); printList(list);
    list = reverseList(list);
    printf("逆轉後："); printList(list);
    freeList(list);  // 良好習慣：釋放所有節點
    return 0;
}