單向鏈表反轉：C 語言完整實現與圖解邏輯

演算法核心思想

鏈表反轉本質是將每個節點的 next 指標從指向「下一個節點」改為指向「前一個節點」。採用三指標迭代法：

• head：當前待處理節點
• mid：已反轉部分的新頭節點
• last：mid 的前驅（上一輪的 mid）

完整程式碼架構

節點定義與基本操作

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

鏈表建立 createllist()

依陣列順序建立節點，返回頭指標。注意修正原碼中 ptr->next = NULL 重複賦值的邏輯瑕疵。

核心反轉函數 invertllist()

llink invertllist(llink head) {
    llink mid = NULL, last = NULL;
    while (head != NULL) {
        last = mid;           // 保存前一輪新頭
        mid = head;           // 當前節點成為新頭
        head = head->next;    // 推進原鏈表
        mid->next = last;     // 反轉指標指向
    }
    return mid;               // 返回新頭指標
}

輔助功能

• printllist()：遍歷輸出節點值
• freellist()：釋放所有節點記憶體

main() 測試流程

int main() {
    int arr[6] = {1,2,3,4,5,6};
    llink head = createllist(arr, 6);
    printllist(head);          // 輸出: [1][2][3][4][5][6]
    head = invertllist(head);
    printllist(head);          // 輸出: [6][5][4][3][2][1]
    freellist(head);
    return 0;
}

圖解迭代過程

初始：1 → 2 → 3 → NULL

第 1 輪：mid=1, last=NULL → 1 → NULL

第 2 輪：mid=2, last=1 → 2 → 1 → NULL

第 3 輪：mid=3, last=2 → 3 → 2 → 1 → NULL

複雜度與注意事項

• 時間 O(n)，空間 O(1)
• 原碼 createllist() 中有 ptr->next = NULL 連續兩行，第二行覆蓋第一行，屬冗餘
• main() 末尾重複呼叫 printllist(head) 兩次，屬筆誤