使用std::list::reverse可直接反转双向链表;手动反转单链表常用三指针迭代法或递归法,前者时间O(n)空间O(1),后者简洁但占栈空间。

在C++中,反转链表是一个常见的数据结构操作。根据使用的是标准库容器还是自定义的链表结构,实现方式有所不同。本文将介绍两种主要方法:使用 std::list 的内置 reverse 方法,以及手动实现单链表的反转算法。
使用 std::list 的 reverse 方法
如果你使用的是 C++ 标准库中的 std::list(双向链表),可以直接调用其成员函数 reverse() 来反转元素顺序。
这个方法高效且无需手动编写逻辑,底层由标准库优化实现。
#include <list>
#include <iostream>
<p>int main() {
std::list<int> lst = {1, 2, 3, 4, 5};</p><pre class='brush:php;toolbar:false;'>lst.reverse(); // 直接反转
for (const auto& val : lst) {
std::cout << val << " ";
}
// 输出: 5 4 3 2 1
return 0;}
立即学习“C++免费学习笔记(深入)”;
注意:该方法仅适用于 std::list,不适用于 std::vector 或原生指针实现的链表。若要反转 vector,可使用 std::reverse(vec.begin(), vec.end())。
手动实现单链表反转(算法)
在面试或实际算法题中,更常见的是对一个手写单向链表进行反转。此时需要自己实现反转逻辑,通常采用“三指针法”迭代完成。
假设链表节点定义如下:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
反转函数实现:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
<pre class='brush:php;toolbar:false;'>while (curr != nullptr) {
ListNode* nextTemp = curr->next; // 保存下一个节点
curr->next = prev; // 反转当前节点指针
prev = curr; // 移动 prev 前进
curr = nextTemp; // 移动 curr 前进
}
return prev; // 新的头节点}
立即学习“C++免费学习笔记(深入)”;
该算法时间复杂度为 O(n),空间复杂度为 O(1),是效率较高的解法。
递归方式实现反转
也可以用递归思路实现链表反转,虽然代码更简洁,但会占用 O(n) 的调用栈空间。
ListNode* reverseListRecursive(ListNode* head) {
if (!head || !head->next) {
return head;
}
<pre class='brush:php;toolbar:false;'>ListNode* newHead = reverseListRecursive(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;}
立即学习“C++免费学习笔记(深入)”;
递归的核心思想是:先将当前节点之后的部分完全反转,然后调整当前节点与后续节点的关系,最终返回新的头节点。
基本上就这些。对于日常开发,优先使用 std::list::reverse();在算法练习中,掌握迭代和递归两种手动实现方式更有价值。理解指针的变换过程是关键。不复杂但容易忽略细节,比如空指针判断和连接断开顺序。










