鏈表逆轉與陣列逆轉的本質差異：指標操作與記憶體策略深度解析

面試經典題目「鏈表逆轉」考驗的不僅是指標操作，更是對資料結構記憶體模型的理解。本文對比連續記憶體（陣列）逆轉與單向鏈表逆轉的實作邏輯，揭示兩者在空間複雜度、操作模式上的本質不同。

一、連續記憶體陣列逆轉：以空間換時間

STATUS normal_revert(int array[], int length) {
    if (NULL == array || 0 == length) return FALSE;
    int* pData = (int*)malloc(sizeof(int) * length);
    assert(NULL != pData);
    memset(pData, 0, sizeof(int) * length);

    int index = length - 1;
    while (index >= 0) {
        pData[length - 1 - index] = array[index];
        index--;
    }
    memmove(array, pData, length * sizeof(int));
    free(pData);
    return TRUE;
}

核心步驟：
1. 分配等大臨時陣列 pData
2. 從原陣列尾端向前拷貝至臨時陣列頭端
3. memmove 覆蓋原陣列並釋放臨時空間
特點：需 O(N) 額外空間，時間複雜度 O(N)，操作直觀但空間效率低。

二、單向鏈表逆轉：原地指標重組

STATUS link_revert(NODE** pNode) {
    if (NULL == pNode || NULL == *pNode) return FALSE;
    NODE* pPrevNode = NULL;
    NODE* pNextNode = (*pNode)->next;
    (*pNode)->next = NULL; // 原頭節點變尾節點

    while (pNextNode) {
        pPrevNode = pNextNode;           // 當前待處理節點
        pNextNode = pNextNode->next;     // 保存下一節點
        pPrevNode->next = *pNode;        // 反轉指向
        *pNode = pPrevNode;              // 更新新頭節點
    }
    return TRUE;
}

核心邏輯（三指標協作）：
1. pNode：指向已逆轉部分的頭節點（雙重指標可修改呼叫端頭指標）
2. pPrevNode：當前正在處理、即將加入已逆轉部分的節點
3. pNextNode：保存下一個待處理節點，防止鏈斷
過程：將原鏈表拆分為「已逆轉區」與「待逆轉區」，逐個將待逆轉區節點移至已逆轉區頭部。

三、本質差異總結

結語

陣列逆轉是「搬資料」，鏈表逆轉是「改關係」。後者展現了指標操作的精髓：在不移動資料的前提下，僅透過重組 next 指標即可實現邏輯逆序。建議讀者在紙上畫圖追蹤三指標變化，體會「原地逆轉」的優雅。