C語言實現單向鏈表反轉：從基礎操作到完整代碼詳解

鏈表反轉核心邏輯

單向鏈表反轉是數據結構中的經典操作，本質上是將節點的 next 指針方向逐個逆轉。以鏈表 a→b→c→d→e→NULL 為例，反轉後變為 e→d→c→b→a→NULL。操作需維護三個指針：head（當前節點）、mid（新鏈表頭）、last（已反轉部分的尾部）。

逐步反轉演示

初始狀態：head→a，mid=NULL，last=NULL。循環執行：

1. last = mid（保存前一狀態）
2. mid = head（當前節點成為新頭）
3. head = head→next（推進到下一節點）
4. mid→next = last（斷開原鏈接，指向已反轉部分）

重複直到 head==NULL，此時 mid 指向反轉後的新頭節點。

完整可運行代碼

#include <stdlib.h>
#include <stdio.h>

struct llist {
    int num;
    struct llist *next;
};
typedef struct llist node;
typedef node *llink;

/* 列印鏈表 */
void printllist(llink ptr) {
    while (ptr != NULL) {
        printf("[%d]", ptr->num);
        ptr = ptr->next;
    }
    printf("\n");
}

/* 建立鏈表 */
llink createllist(int *array, int len) {
    llink head = (llink)malloc(sizeof(node));
    if (!head) return NULL;
    head->num = array[0];
    head->next = NULL;
    llink ptr = head;
    for (int i = 1; i < len; i++) {
        llink ptr1 = (llink)malloc(sizeof(node));
        if (!ptr1) return NULL;
        ptr1->num = array[i];
        ptr1->next = NULL;
        ptr->next = ptr1;
        ptr = ptr->next;
    }
    return head;
}

/* 反轉鏈表核心函數 */
llink invertllist(llink head) {
    llink mid = NULL, last;
    while (head != NULL) {
        last = mid;
        mid = head;
        head = head->next;
        mid->next = last;
    }
    return mid;
}

/* 釋放記憶體 */
void freellist(llink head) {
    llink ptr;
    while (head != NULL) {
        ptr = head;
        head = head->next;
        free(ptr);
    }
}

int main() {
    int data[6] = {1, 2, 3, 4, 5, 6};
    llink head = createllist(data, 6);
    if (!head) {
        printf("記憶體配置失敗!\n");
        return 1;
    }
    printf("原鏈表: ");
    printllist(head);
    head = invertllist(head);
    printf("反轉後: ");
    printllist(head);
    freellist(head);
    return 0;
}

關鍵點總結

• 時間複雜度 O(n)，空間複雜度 O(1)
• 需妥善處理記憶體分配失敗情況
• 反轉後原頭節點變為尾節點，next 指向 NULL
• 適用於單向鏈表，雙向鏈表需同步修改 prev 指針