單鏈表逆序：遞歸與迭代四種變體完整實現

節點定義

typedef int Item;
typedef struct node {
    Item item;
    struct node *next;
} Node, *List;

不帶頭節點：逆序返回新頭指針

迭代法（三指針法）

List reverse1(List l)
{
    Node *p1, *p2;
    if (l == NULL) return l;
    p1 = l->next;
    l->next = NULL;        // 原頭變尾
    while (p1 != NULL) {
        p2 = p1->next;     // 保存下一個
        p1->next = l;      // 反轉指針
        l = p1;            // l 移動到新頭
        p1 = p2;
    }
    return l;
}

遞歸法（頭插法思想）

List reverse2(List l)
{
    if (l == NULL || l->next == NULL) return l;
    Node *p = reverse2(l->next); // 遞歸處理子表，返回新頭
    l->next->next = l;           // 當前節點插到子表尾部
    l->next = NULL;              // 斷開原連接
    return p;                    // 傳遞新頭
}

帶頭節點：原地逆序，頭節點不變

迭代法

void reverse3(List l)  // l 是頭節點
{
    Node *p1, *p2, *p3;
    if (l == NULL || l->next == NULL) return;
    p1 = l->next;
    p2 = p1->next;
    p1->next = NULL;           // 首節點變尾
    while (p2 != NULL) {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    l->next = p1;              // 頭節點指向新首節點
}

遞歸法（需外部判空）

void reverse4(List l, Node *first) // first 為首個數據節點
{
    if (first == NULL || first->next == NULL) {
        l->next = first;         // 遞歸終點：first 為新首節點
        return;
    }
    reverse4(l, first->next);
    first->next->next = first;   // 反轉
    first->next = NULL;
}
// 調用：if (head) reverse4(head, head->next);

複雜度與選擇指南

常見錯誤避坑

• 忘記將原頭節點 next 置 NULL，導致環狀鏈表。
• 遞歸版未正確傳遞新頭指針（reverse2 必須 return p）。
• 帶頭節點版未更新頭節點的 next 指向新首節點。

現代 C++ 推薦寫法

// 迭代，無頭節點，使用 std::unique_ptr 管理內存
Node* reverse(Node* head) {
    Node* prev = nullptr;
    while (head) {
        Node* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}