C++ 怎么实现链表反转 C++ 单链表头插法与递归反转代码【数据结构】

头插法反转单链表通过边遍历边头插实现，时间O(n)、空间O(1)；递归法从尾部回溯修改指针，时间O(n)、空间O(n)，易栈溢出。两者均需处理空链表、单节点及野指针等边界。

头插法反转单链表：边遍历边重建链表结构

头插法本质是用原链表节点逐个插入到新链表头部，从而自然实现顺序翻转。关键在于维护两个指针：cur 指向当前待处理节点，new_head 指向已反转部分的头节点。

• 必须先保存 cur->next，否则断开后无法访问后续节点
• cur 插入新链表时，要让 cur->next = new_head，再更新 new_head = cur
• 初始时 new_head 应为 nullptr，避免野指针或未定义行为

ListNode* reverseList(ListNode* head) {
    ListNode* new_head = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* next = cur->next;  // 保存下一个节点
        cur->next = new_head;         // 头插
        new_head = cur;               // 更新新头
        cur = next;
    }
    return new_head;
}

递归反转：从尾节点开始逐层回溯修改指针

递归解法不新建节点，而是靠函数调用栈“记住”倒数第二个节点，等递归到达尾节点（head->next == nullptr）后，一层层把后继节点的 next 指向前驱。

• 递归终止条件必须是 head == nullptr || head->next == nullptr，缺一不可，否则空指针解引用
• 递归返回的是原链表的尾节点，也就是反转后的头节点，全程只返回这一个指针
• 回溯时执行 head->next->next = head，然后立即置 head->next = nullptr，否则会成环

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

两种方法的性能与适用场景差异

头插法时间复杂度 O(n)，空间 O(1)，适合对内存敏感或需迭代控制的场景；递归法时间也是 O(n)，但空间 O(n)（栈深度），在链表极长时可能栈溢出。

• LeetCode 等平台测试用例通常较短，递归写法简洁不易错，但生产代码中应优先考虑迭代
• 若链表节点含非 trivial 析构逻辑（如持有资源），递归更深意味着资源释放延迟更久
• 头插法可轻松改造成「反转指定区间」或「每 k 个一组反转」，扩展性更强

容易被忽略的边界：空链表、单节点、野指针检查

几乎所有初学者写的反转代码，在 head == nullptr 或 head->next == nullptr 时逻辑都看似正确，但一旦涉及二级指针操作（比如传入 ListNode** head 做就地修改），漏掉空检查就会直接崩溃。

立即学习“C++免费学习笔记（深入）”；

• 头插法中若忘记 cur = next，循环会卡死在第一个节点
• 递归中若漏写 head->next = nullptr，原头节点仍指向第二个节点，导致反转后链表成环
• 使用前务必确认 ListNode 定义中 next 成员是否初始化为 nullptr，否则未初始化指针反转后行为不可预测