C++ 單鏈表逆序實現：遞歸法與迭代法完整可運行代碼

遞歸逆序（教學演示）

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int v): data(v), next(nullptr) {}
};

void ReverseRecursive(Node* cur, Node*& head) {
    if (!cur || !cur->next) { head = cur; return; }
    ReverseRecursive(cur->next, head);
    cur->next->next = cur;
    cur->next = nullptr;
}

// 迭代逆序（生產推薦，O(1) 空間）
void ReverseIterative(Node*& head) {
    Node *prev = nullptr, *curr = head;
    while (curr) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}

// 輔助：創建、打印、釋放
Node* CreateList(int n) {
    Node *head = nullptr, *tail = nullptr;
    for (int i = 1; i <= n; ++i) {
        Node* p = new Node(i);
        if (!head) head = tail = p;
        else { tail->next = p; tail = p; }
    }
    return head;
}
void Print(Node* head) {
    for (Node* p = head; p; p = p->next) cout << p->data << ' ';
    cout << '\n';
}
void Free(Node* head) {
    while (head) { Node* t = head; head = head->next; delete t; }
}

int main() {
    Node* list = CreateList(6);
    Print(list);           // 1 2 3 4 5 6
    ReverseRecursive(list, list);
    Print(list);           // 6 5 4 3 2 1
    ReverseIterative(list);
    Print(list);           // 1 2 3 4 5 6
    Free(list);
    return 0;
}

關鍵點

• 遞歸本質：利用調用棧保存後續節點，回溯時反轉指針。
• 迭代三指針 `prev/curr/next` 更高效、無棧溢出風險。
• 頭指針需傳引用 `Node*&` 以便修改實際頭節點。

總結

單鏈表逆序：教學用遞歸理解指針反轉邏輯，工程用迭代法保證性能與穩定性。