單鏈表反轉的三種經典算法實現與圖解

題目

輸入單鏈表頭節點，原地反轉鏈表，返回新頭節點。節點定義：

struct ListNode {
    int m_nKey;
    ListNode* m_pNext;
};

方法一：頭插法構建新鏈表

創建新頭節點 newList，遍歷原鏈表，將每個節點從原鏈表摘下，插入 newList 之後（即新鏈表頭部）。最終釋放原頭節點。

LinkedList ReverseSinglyLinkedList(LinkedList list) {
    LinkedList newList = (LinkedList)malloc(sizeof(LNode));
    if (!list || !newList) return NULL;
    newList->data = list->data;
    newList->next = NULL;

    while (list->next) {
        LNode* tmp = newList->next;        // 保存新鏈表後續
        newList->next = list->next;        // 摘下原第一個節點
        list->next = list->next->next;     // 原鏈表跳過該節點
        newList->next->next = tmp;         // 恢復新鏈表後續
    }
    free(list);
    return newList;
}

方法二：原地前移法（就地反轉）

維持原頭節點不動，依次將「當前第一個節點的下一個節點」移動到頭節點之後。

圖解過程：
初始：Header → 1 → 2 → 3 → 4 → NULL
第1輪：移動 2 到 Header 後 → Header → 2 → 1 → 3 → 4
第2輪：移動 3 到 Header 後 → Header → 3 → 2 → 1 → 4
第3輪：移動 4 到 Header 後 → Header → 4 → 3 → 2 → 1 → NULL

LinkedList ReverseSinglyLinkedList(LinkedList list) {
    if (!list) return NULL;
    LNode* tmp = list->next;
    while (tmp->next) {
        LNode* p = tmp->next;      // 要前移的節點
        tmp->next = p->next;       // tmp 跳過 p
        p->next = list->next;      // p 指向原第一個
        list->next = p;            // 頭節點指向 p
    }
    return list;
}

方法三：尾插法構建反序鏈表

思路與方法二對稱：將原鏈表前段節點依次移動到原尾節點之後。代碼結構相似，不再贅述。

面試核心考點

1. 邊界處理：空鏈表、單節點、雙節點。
2. 指針操作順序：先保存後續，再斷開重連，避免丟失節點。
3. 空間複雜度：方法一 O(1) 額外空間（僅新頭節點），方法二/三 真正 O(1) 原地操作。
4. 代碼健壯性：先分析再編碼，給面試官留下「設計優於編碼」的印象。