在数据结构中，链表是一种非常重要的线性数据结构。单向链表作为链表的一种，其特点是数据元素之间是单向链接的。在某些场景下，我们可能需要对单向链表进行反转操作。本文将详细介绍如何使用C++通过递归和非递归两种方式来反转单向链表。
一、单向链表的基本概念
单向链表是一种线性数据结构，由节点（Node）组成，每个节点包含一个数据域和一个指向下一个节点的指针。单向链表只能从头节点开始，沿一个方向遍历整个链表。
二、递归方式反转单向链表
递归反转链表的思路是从链表的尾部开始，逐个将节点的指针反向。递归函数需要处理两个主要问题：基本情况（Base Case）和递归情况（Recursive Case）。
基本思路：
- 如果链表为空或只有一个节点，则无需反转，直接返回原链表。
- 否则，递归反转子链表，并将当前节点的next指针指向反转后的子链表的头部。
代码实现：
#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 递归反转链表函数
ListNode* reverseListRecursive(ListNode* head) {
// 基本情况
if (head == nullptr || head->next == nullptr) {
return head;
}
// 递归情况
ListNode* newHead = reverseListRecursive(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
// 打印链表函数
void printList(ListNode* head) {
while (head != nullptr) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
}
int main() {
// 创建一个简单的链表: 1 -> 2 -> 3 -> 4
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
std::cout << "原始链表: ";
printList(head);
ListNode* newHead = reverseListRecursive(head);
std::cout << "反转后的链表: ";
printList(newHead);
// 清理内存...
return 0;
}在上面的代码中，reverseListRecursive 函数通过递归方式反转链表。基本情况是当链表为空或只有一个节点时，直接返回该节点。递归情况是反转当前节点的子链表，并将当前节点添加到反转后子链表的末尾。
三、非递归方式反转单向链表
非递归反转链表的思路是遍历链表，逐个调整节点间的指针方向。
基本思路：
- 初始化前一个节点（prev）为nullptr，当前节点（curr）为头节点。
- 遍历链表，每次迭代都将当前节点的next指针指向前一个节点，然后移动prev和curr指针。
- 遍历结束后，新的头节点将是原链表的尾节点。
代码实现：
// 非递归反转链表函数
ListNode* reverseListIterative(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next; // 暂存下一个节点
curr->next = prev; // 反转指针方向
prev = curr; // 前一个节点后移
curr = nextTemp; // 当前节点后移
}
return prev; // 当curr为空时，prev就是新的头节点
}在上面的代码中，reverseListIterative 函数通过迭代方式反转链表。使用两个指针prev和curr来分别追踪前一个节点和当前节点。在遍历过程中，不断调整指针方向，直到遍历完整个链表。
四、总结
本文介绍了如何在C++中使用递归和非递归两种方式反转单向链表。递归方法简洁而优雅，但可能导致堆栈溢出对于非常长的链表。非递归方法则更加直观且对空间的需求较小，是处理大数据集时的更好选择。在实际应用中，应根据具体情况选择合适的方法。
正文完
