LeetCode 206 反轉鏈表：三指針迭代法原地反轉

問題描述

給定單鏈表頭節點，反轉鏈表並返回新頭節點。例如 1→2→3→4→5 → 5→4→3→2→1。

核心算法：三指針迭代原地反轉

維護三個指針：

• prev：已反轉部分的頭節點（初始 nullptr）。
• curr：當前待處理節點（初始 head）。
• next：暫存 curr->next 防止丟失。

逐步操作

while (curr) {
    next = curr->next;  // 1. 保存下一節點
    curr->next = prev;  // 2. 反轉指針
    prev = curr;        // 3. prev 前進
    curr = next;        // 4. curr 前進
}
return prev; // 最後 prev 是新頭節點

完整代碼 (C++)

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

關鍵點

• 保存 next：斷開 curr->next 前必須先存 next，否則後續鏈表丟失。
• 返回 prev：循環結束時 curr==nullptr，prev 指向原尾節點（新頭）。
• 空鏈表處理：head==nullptr 直接返回 nullptr，代碼天然兼容。

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}