鏈表逆轉完全指南：從陣列到單向鏈表的演進

鏈表逆轉是面試經典題目，也是實際開發中常見需求。與連續記憶體（陣列）的逆轉截然不同，單向鏈表因節點分散、僅有單向指標，必須逐節點調整指向。本文對比兩種資料結構的逆轉邏輯，帶你深入理解指標操作的精髓。

一、連續記憶體（陣列）逆轉

陣列逆轉直觀簡單：配置等大暫存空間，從尾端向前複製，再覆寫回原陣列。

STATUS normal_revert(int array[], int length) {
    if (!array || length == 0) return FALSE;

    int* temp = (int*)malloc(sizeof(int) * length);
    assert(temp);
    memset(temp, 0, sizeof(int) * length);

    for (int i = length - 1, j = 0; i >= 0; --i, ++j)
        temp[j] = array[i];

    memmove(array, temp, length * sizeof(int));
    free(temp);
    return TRUE;
}

關鍵步驟： 1) 分配暫存空間 2) 逆序複製 3) 覆寫原陣列並釋放暫存。

二、單向鏈表逆轉：三指標迭代法

鏈表無法隨機存取，必須在遍歷過程中即時反轉 next 指標。經典解法維護三個指標：

• pNode：已逆轉部分的新頭節點
• pPrevNode：當前處理節點
• pNextNode：下一個待處理節點（防斷鏈）

STATUS link_revert(NODE** ppHead) {
    if (!ppHead || !*ppHead) return FALSE;

    NODE* pPrev = NULL;
    NODE* pCurr = *ppHead;
    NODE* pNext = NULL;

    while (pCurr) {
        pNext = pCurr->next;   // 1. 保存下一節點
        pCurr->next = pPrev;   // 2. 反轉當前指標
        pPrev = pCurr;         // 3. 推進：已逆轉部分前移
        pCurr = pNext;         // 4. 推進：處理下一節點
    }

    *ppHead = pPrev;           // 新頭節點
    return TRUE;
}

三、核心差異總結

理解這兩者的本質區別，不僅能應付面試，更能在系統級開發中靈活選擇適合的資料結構與演算法策略。