反转链表可通过迭代和递归实现。迭代法用三个指针逐个翻转，时间O(n)空间O(1)；递归法利用栈回溯处理后续节点，逻辑清晰但空间O(n)，易栈溢出。生产环境推荐迭代，学习递归思想可用递归。
反转链表是C++数据结构中的经典问题，常用于面试和实际开发中。单链表由于其单向性，反转操作需要调整每个节点的指针方向。下面介绍两种常用方法：非递归（迭代）和递归实现。
使用三个指针分别指向当前节点、前一个节点和下一个节点，逐个翻转指针方向。
核心思路：从头节点开始，将每个节点的 next 指向前驱节点，直到遍历完整个链表。
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
<p>ListNode<em> reverseList(ListNode</em> head) {
ListNode<em> prev = nullptr; // 前一个节点
ListNode</em> curr = head; // 当前节点
while (curr != nullptr) {
ListNode* nextTemp = curr->next; // 临时保存下一个节点
curr->next = prev; // 反转指针
prev = curr; // 移动 prev
curr = nextTemp; // 移动 curr
}
return prev; // 新的头节点
}</p>该方法时间复杂度为 O(n)，空间复杂度为 O(1)，效率高且稳定。
立即学习“C++免费学习笔记（深入）”；
利用函数调用栈回溯的特性，在递归到底后逐层反转指针。
关键点：假设当前节点之后的所有节点已经反转完成，只需处理当前节点与后续节点的关系。
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) 的栈空间，对于极长链表可能引发栈溢出。
基本上就这些。掌握这两种写法有助于深入理解指针操作和递归机制。
以上就是C++如何反转链表_C++单链表反转算法的递归与非递归实现的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
647
收藏
