C 語言單向鏈表反轉演算法完整實作與測試

反轉函式

typedef struct _node {
    int data;
    struct _node *next;
} node;

node* reverse1(node *head) {
    node *p, *q, *r;
    if (head != NULL) {
        p = head;
        q = head->next;
        head->next = NULL; // 原頭節點變尾，next 置 NULL
        while (q) {
            r = q->next;   // 暫存下一節點
            q->next = p;   // 反轉指向
            p = q;         // p 前進
            q = r;         // q 前進
        }
        head = p;          // 新頭節點
    }
    return head;
}

測試主程式

int main(void) {
    node *link = NULL, *tmp = NULL;
    // 建立 0->1->2->3->4 (頭插法)
    for (int i = 0; i < 5; i++) {
        tmp = malloc(sizeof(node));
        tmp->data = i;
        tmp->next = link;
        link = tmp;
    }
    // 列印原鏈表
    tmp = link;
    printf("before reversal:\n");
    while (tmp) { printf("%d ", tmp->data); tmp = tmp->next; }
    putchar('\n');

    link = reverse1(link);

    // 列印反轉後
    tmp = link;
    printf("after reversal:\n");
    while (tmp) { printf("%d ", tmp->data); tmp = tmp->next; }
    putchar('\n');
    return 0;
}

執行結果

before reversal:
4 3 2 1 0
after reversal:
0 1 2 3 4

演算法解析

• 三指標 p, q, r 迭代：p 指向已反轉部分的頭，q 指向待反轉節點，r 暫存 q->next 防斷鏈。
• 時間複雜度 O(n)，空間複雜度 O(1)。
• 遞歸版本雖簡潔但棧深度受限，生產環境推薦迭代版。

常見錯誤

• 忘記將原頭節點 next 設為 NULL，導致成環。
• 未處理 head == NULL 或單節點情況。
• 反轉後未更新外部頭指標（需回傳新頭或雙重指標參數）。