C++基础（④链表反转（链表 + 迭代 / 递归））

链表反转（链表 + 迭代 / 递归）
题目描述：给你单链表的头节点 head，请你反转链表，并返回反转后的链表头节点。
示例：输入链表 1→2→3→4→5 → 输出 5→4→3→2→1。
思路提示：

迭代法：用三个指针 prev（前一个节点，初始 nullptr）、curr（当前节点，初始 head）、next（临时存储下一个节点），遍历链表时依次修改 curr->next = prev，再更新三个指针。
递归法：递归反转 head 的下一个节点，再将 head 接到反转后的链表尾部，时间复杂度 O (n)，空间复杂度 O (n)（递归栈）。
 

#include <iostream>

using namespace std;

// ---------- 1. 节点定义 ----------
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v = 0, ListNode* n = nullptr) : val(v), next(n) {}
};

// ---------- 2. 迭代法 ----------
ListNode* reverseList_iter(ListNode* head) {
    ListNode* prev = nullptr;   // 新链表的头
    ListNode* curr = head;      // 正在处理的节点
    while (curr) {
        ListNode* nextTmp = curr->next; // 临时保存下一个
        curr->next = prev;             // 反向
        prev = curr;                   // prev 前进一步
        curr = nextTmp;                // curr 前进一步
    }
    return prev;  // prev 变成新头节点
}

// ---------- 3. 递归法 ----------
ListNode* reverseList_recur(ListNode* head) {
    if (!head || !head->next) return head;   // 空或最后一个节点
    ListNode* newHead = reverseList_recur(head->next); // 先反转后面的链表
    head->next->next = head;   // 把当前节点接到已反转部分的尾巴
    head->next = nullptr;      // 防止成环
    return newHead;
}

// ---------- 4. 辅助：打印链表 ----------
void printList(ListNode* head) {
    for (ListNode* p = head; p; p = p->next)
        cout << p->val << (p->next ? "→" : "");
    cout << endl;
}

// ---------- 5. 测试 ----------
int main() {
    // 构造 1→2→3→4→5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    cout << "Original: "; printList(head);

    // 迭代版
    ListNode* newHead_iter = reverseList_iter(head);
    cout << "Reversed (iter): "; printList(newHead_iter);

    // 递归版（再反转回来演示）
    ListNode* newHead_recur = reverseList_recur(newHead_iter);
    cout << "Re-reversed (recur): "; printList(newHead_recur);

    return 0;
}

拆解 1：构造函数的参数与默认值
构造函数 ListNode(int v = 0, ListNode* n = nullptr) 有两个参数：

int v：用于初始化 val（节点数据），默认值为 0
ListNode* n：用于初始化 next（下一个节点指针），默认值为 nullptr（空指针）

默认参数的作用：调用构造函数时，可以不传参数、传 1 个参数或传 2 个参数，非常灵活。

拆解 2：初始化列表 : val(v), next(n)
这是 C++ 的初始化列表语法，作用是在构造函数体执行前，直接初始化成员变量：

val(v)：将成员变量 val 初始化为参数 v 的值
next(n)：将成员变量 next 初始化为参数 n 的值

相比在构造函数体内赋值（如 val = v;），初始化列表更高效，尤其适合 const 成员或自定义类型成员的初始化。