C 語言單鏈表就地逆置：O(1) 空間迭代法完整實現

單鏈表就地逆置是經典面試題，要求不分配新節點、僅用 O(1) 輔助空間，通過修改指針方向實現。本文給出標準三指針迭代法代碼並圖解過程。

核心算法：三指針迭代

typedef struct Node {
    int value;
    struct Node *next;
} Node;

void reverse(Node **head) {          // 傳頭指針的地址，以便修改頭節點
    Node *prev = NULL;
    Node *curr = *head;
    Node *next = NULL;

    while (curr != NULL) {
        next = curr->next;   // 1. 暫存下一個節點
        curr->next = prev;   // 2. 反轉當前節點指針
        prev = curr;         // 3. prev 後移
        curr = next;         // 4. curr 後移
    }
    *head = prev;            // 5. 更新頭指針
}

步驟圖解（以 1→2→3→NULL 為例）

初始:  prev=NULL  curr=1  next=?
循環1: next=2     1->NULL  prev=1    curr=2
循環2: next=3     2->1     prev=2    curr=3
循環3: next=NULL   3->2     prev=3    curr=NULL
結束:  head=3     3->2->1->NULL

完整可運行程序

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

typedef struct Node {
    int value;
    struct Node *next;
} Node;

Node* create_list(int n) {
    Node *head = NULL, *tail = NULL;
    for (int i = 1; i <= n; i++) {
        Node *p = malloc(sizeof(Node));
        p->value = i;
        p->next = NULL;
        if (!head) head = tail = p;
        else { tail->next = p; tail = p; }
    }
    return head;
}

void print_list(Node *head) {
    while (head) {
        printf("%d -> ", head->value);
        head = head->next;
    }
    puts("NULL");
}

void reverse(Node **head) {
    Node *prev = NULL, *curr = *head, *next;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}

int main() {
    Node *head = create_list(5);
    printf("原序列: "); print_list(head);
    reverse(&head);
    printf("逆置後: "); print_list(head);
    return 0;
}

遞歸版（空間 O(n)，僅供理解）

Node* reverse_rec(Node *head) {
    if (!head || !head->next) return head;
    Node *new_head = reverse_rec(head->next);
    head->next->next = head;
    head->next = NULL;
    return new_head;
}

常見錯誤

• 忘記暫存 next 導致鏈表斷裂。
• 函數參數用 Node *head 而非 Node **head，無法修改調用者的頭指針。
• 空鏈表、單節點鏈表未處理（上述代碼天然兼容）。

掌握「暫存→反轉→後移」三步驟，即可在任何場合寫出正確的就地逆置代碼。