C++如何反转链表_C++单链表反转算法的递归与非递归实现

反转链表可通过迭代和递归实现。迭代法用三个指针逐个翻转，时间O(n)空间O(1)；递归法利用栈回溯处理后续节点，逻辑清晰但空间O(n)，易栈溢出。生产环境推荐迭代，学习递归思想可用递归。

反转链表是C++数据结构中的经典问题，常用于面试和实际开发中。单链表由于其单向性，反转操作需要调整每个节点的指针方向。下面介绍两种常用方法：非递归（迭代）和递归实现。

非递归方式反转链表

使用三个指针分别指向当前节点、前一个节点和下一个节点，逐个翻转指针方向。

核心思路：从头节点开始，将每个节点的 next 指向前驱节点，直到遍历完整个链表。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
ListNode reverseList(ListNode head) {
ListNode prev = nullptr;   // 前一个节点
ListNode curr = head;      // 当前节点
while (curr != nullptr) {
ListNode* nextTemp = curr->next;  // 临时保存下一个节点
curr->next = prev;                // 反转指针
prev = curr;                      // 移动 prev
curr = nextTemp;                  // 移动 curr
}
return prev;  // 新的头节点
}

该方法时间复杂度为 O(n)，空间复杂度为 O(1)，效率高且稳定。

递归方式反转链表

利用函数调用栈回溯的特性，在递归到底后逐层反转指针。

关键点：假设当前节点之后的所有节点已经反转完成，只需处理当前节点与后续节点的关系。

ListNode* reverseListRecursive(ListNode* head) {
    // 终止条件：空节点或只有一个节点
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    // 递归反转后面的节点
    ListNode* newHead = reverseListRecursive(head->next);
    // 让后一个节点指向当前节点
    head->next->next = head;
    // 当前节点的 next 置为空，防止成环
    head->next = nullptr;
    return newHead;  // 返回新的头节点
}

递归写法简洁，但会消耗 O(n) 的栈空间，对于极长链表可能引发栈溢出。

两种方法对比与使用建议

• 迭代法更安全，适合生产环境，尤其在链表较长时优先选用
• 递归法逻辑清晰，适合理解递归思想，但在性能要求高或资源受限场景慎用
• 两者时间复杂度均为 O(n)，但空间开销不同

基本上就这些。掌握这两种写法有助于深入理解指针操作和递归机制。

# 但在  # 只需  # 均为  # 两种  # 迭代  # 数据结构  # 递归  # c++  # 指针  # 栈  # node  # 算法  # 遍历  # 链表  # 法利 

相关栏目： <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 AI推广<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 SEO优化<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 技术百科<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 谷歌推广<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 百度推广<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 网络营销<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 案例网站<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 精选文章<？ｍｕｍａ echo $count; ?> 】