1. 概览
为何需要单链表反转
C++ 单链表反转算法在很多实际场景中用于将链表的顺序颠倒，以便于后续的遍历、合并、或对称性处理。通过反转，可以在不额外申请新节点的情况下改变数据线性组合的方向，从而提升一些操作的效率。
在数据结构学习中，单链表反转是考察指针操作与内存管理能力的经典题目。完整示例通常包含节点定义、两种实现方式（迭代与递归）以及一个简短的演示代码，帮助读者对比思路与实现要点。
2. 数据结构与实现准备
节点定义与基本操作
在 C++ 中，单链表通常由一个节点结构组成：ListNode 包含一个值域和指向下一个节点的指针。正确的构造函数有助于快速创建节点并避免空指针错误。
为了演示完整流程，需要提供构建链表和打印链表的辅助函数，以便观察反转前后的变化。下面的定义在实际项目中也能直接复用。
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 构建链表
ListNode* buildList(const std::initializer_list& vals) {ListNode* head = nullptr;ListNode* tail = nullptr;for (int v : vals) {ListNode* node = new ListNode(v);if (!head) {head = tail = node;} else {tail->next = node;tail = node;}}return head;
}// 打印链表
void printList(ListNode* head) {for (ListNode* p = head; p; p = p->next) {std::cout << p->val << (p->next ? " -> " : "");}std::cout << std::endl;
}
3. 迭代法反转算法
算法思路与关键步骤
迭代法核心在于使用两到三个指针在遍历过程中逐步<反转指针指向，以实现就地 reversals。最常见的做法是维护 prev、cur，以及在循环中临时保存 cur->next 的值。
在每一次循环迭代中，先保存 cur->next，再让 cur->next 指向 prev，随后让 prev 与 cur 前进到下一个节点。循环结束时，prev 指向新的头节点。
ListNode* reverseListIter(ListNode* head) {ListNode* prev = nullptr;ListNode* cur = head;while (cur) {ListNode* nxt = cur->next; // 保存下一个节点cur->next = prev; // 反转指针prev = cur; // 移动 prevcur = nxt; // 继续}return prev;
}// 完整示例
int main() {ListNode* head = buildList({1, 2, 3, 4, 5});head = reverseListIter(head);printList(head);return 0;
}
4. 递归法反转算法
递归策略与终止条件
递归实现的思想是：把后续子链反转，然后将当前节点挂在反转后链表的末端。这种做法代码简洁，但需要注意递归深度对栈的影响。
递归的基线条件通常是若头节点为空或只有一个节点，则直接返回头节点；随后进行回溯时将当前节点连到后续链表的末尾，并将自身的 next 指向 null。
ListNode* reverseListRec(ListNode* head) {if (!head || !head->next) return head;ListNode* newHead = reverseListRec(head->next);head->next->next = head;head->next = nullptr;return newHead;
}// 递归示例
int main_rec() {ListNode* head = buildList({1, 2, 3, 4, 5});head = reverseListRec(head);printList(head);return 0;
}
5. 要点解析与对比
关键要点与注意事项
在分析两种实现时，需关注的核心指标包括时间复杂度、空间复杂度以及边界情况。对于两种实现，都需要在链表为空或仅有一个节点时能正确处理。
时间复杂度均为 O(n)，其中 n 是链表长度；空间复杂度在迭代实现中为 O(1)（就地就地反转），而递归实现通常为 O(n) 的栈空间，受到递归深度影响。因此在链表很长时，递归实现可能面临栈溢出风险。
在实际工程中，迭代法因其稳定的栈消耗和对极端输入的鲁棒性，通常作为首选实现；递归法更适合快速原型或教学演示，代码简洁但需要关注模型的栈限制。
