c++ 反转链表递归调用

### C++ 实现反转链表的 PTA 解题思路及代码示例 在解决反转链表的问题时，可以采用迭代或者递归的方法来完成。以下是基于这两种方法的具体实现。 #### 方法一：迭代法 通过遍历原链表并逐步构建新链表的方式实现反转操作。这种方法的空间复杂度较低，因为不需要额外存储整个链表的数据结构[^3]。 ```cpp #include <iostream> using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode *prev = nullptr, *curr = head; while (curr != nullptr) { ListNode* tempNext = curr->next; // 保存当前节点的下一个节点 curr->next = prev; // 当前节点指向前一个节点 prev = curr; // 前移一位 curr = tempNext; // 移动到下一个节点 } return prev; // 返回新的头结点 } void printList(ListNode* head) { while (head != nullptr) { cout << head->val << " "; head = head->next; } cout << endl; } int main() { // 创建测试链表: 1 -> 2 -> 3 -> 4 -> 5 ListNode* node5 = new ListNode(5); ListNode* node4 = new ListNode(4); ListNode* node3 = new ListNode(3); ListNode* node2 = new ListNode(2); ListNode* node1 = new ListNode(1); node1->next = node2; node2->next = node3; node3->next = node4; node4->next = node5; cout << "Original List: "; printList(node1); ListNode* reversedHead = reverseList(node1); cout << "Reversed List: "; printList(reversedHead); return 0; } ``` #### 方法二：递归法 利用函数调用栈自然形成的回溯特性，在返回的过程中调整节点之间的指向关系。虽然递归方法更加简洁优雅，但在处理大规模数据时可能会遇到堆栈溢出的风险[^4]。 ```cpp #include <iostream> using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseListRecursive(ListNode* head) { if (!head || !head->next) return head; // 如果到达最后一个节点，则将其作为新的头部 ListNode* restOfList = reverseListRecursive(head->next); // 反转剩余部分 head->next->next = head; // 将当前节点挂载到下个节点之后 head->next = nullptr; // 断开原始链接以防形成环形列表 return restOfList; // 返回新的头部 } void printList(ListNode* head) { while (head != nullptr) { cout << head->val << " "; head = head->next; } cout << endl; } int main() { // 创建测试链表: 1 -> 2 -> 3 -> 4 -> 5 ListNode* node5 = new ListNode(5); ListNode* node4 = new ListNode(4); ListNode* node3 = new ListNode(3); ListNode* node2 = new ListNode(2); ListNode* node1 = new ListNode(1); node1->next = node2; node2->next = node3; node3->next = node4; node4->next = node5; cout << "Original List: "; printList(node1); ListNode* reversedHead = reverseListRecursive(node1); cout << "Reversed List: "; printList(reversedHead); return 0; } ``` 以上两种方式都可以有效地解决问题，并且可以根据实际需求选择合适的一种方式进行编码实践。

<think>我们正在回答用户关于C++实现链表反转的问题。用户要求提供C++代码实现，我们可以参考之前给出的Python迭代法和递归法思路，但需要转换为C++语法。同时，用户提供的引用中也有C++实现示例，我们可以借鉴。参考引用[1][3][4]中的C++代码，我们可以总结出：1.链表节点定义：通常是一个结构体，包含数据和指向下一个节点的指针。2.迭代法反转链表：使用三个指针（pre,curr,next）遍历链表并逐个反转指针方向。3.递归法反转链表：递归到链表末尾，然后回溯修改指针。注意：引用[3]中给出了完整的迭代法反转函数，引用[2]中提到了反转链表函数的框架。由于用户要求使用C++，我们将分别实现迭代法和递归法，并注意边界条件（如空链表）。步骤：1.定义链表节点结构（ListNode）。2.实现迭代反转函数。3.实现递归反转函数。4.编写打印链表的辅助函数（参考引用[1]中的打印函数）。5.提供简单的测试用例。注意：在递归法中，递归深度为链表长度，对于长链表可能导致栈溢出，所以迭代法更安全。我们将按照以下结构组织回答：-节点定义-迭代法-递归法-测试代码-复杂度分析-相关实践建议同时，根据系统指令，我们将在回答末尾生成相关问题。</think> ### 如何在 C++ 中实现链表反转 下面分别给出迭代法、递归法和封装链表类的完整实现，均符合 C++ 编程规范： #### **1. 链表节点结构定义** ```cpp struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} // 构造函数初始化 }; ``` #### **2. 迭代法实现 ($O(n)/O(1)$)** ```cpp ListNode* reverseList_iterative(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* next_temp = curr->next; // 临时存储下一节点 [^3] curr->next = prev; // 当前节点指针反转 prev = curr; // prev移动至当前 curr = next_temp; // curr移至下一节点 } return prev; // 新链表头节点 } ``` **复杂度**： - 时间复杂度 $O(n)$：遍历整个链表 - 空间复杂度 $O(1)$：仅使用三个指针变量 #### **3. 递归法实现 ($O(n)/O(n)$)** ```cpp ListNode* reverseList_recursive(ListNode* head) { if (!head || !head->next) return head; // 终止条件：空节点或尾节点 ListNode* new_head = reverseList_recursive(head->next); head->next->next = head; // 反转指针方向 [^1] head->next = nullptr; // 断开原指针 return new_head; } ``` **复杂度**： - 时间复杂度 $O(n)$：递归深度等于链表长度 - 空间复杂度 $O(n)$：递归调用栈空间 #### **4. 链表类封装实现** ```cpp class LinkedList { private: ListNode* head; public: LinkedList() : head(nullptr) {} // 反转成员函数（迭代法） void reverse() { ListNode *prev = nullptr, *curr = head; while (curr) { ListNode* next_temp = curr->next; curr->next = prev; prev = curr; curr = next_temp; } head = prev; // 更新头节点 [^2] } // 打印链表（测试用） void print() { ListNode* curr = head; while (curr) { std::cout << curr->val << "→"; curr = curr->next; } std::cout << "∅\n"; } // 添加节点（测试用） void append(int val) { /* 省略实现 */ } }; ``` #### **5. 测试用例** ```cpp int main() { // 创建链表 1→2→3→4→5 ListNode* head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(3); head->next->next->next = new ListNode(4); head->next->next->next->next = new ListNode(5); // 迭代法测试 ListNode* reversed_iter = reverseList_iterative(head); printList(reversed_iter); // 输出：5→4→3→2→1→∅ // 递归法测试（需重建链表） ListNode* head2 = /* 重建原始链表 */; ListNode* reversed_rec = reverseList_recursive(head2); printList(reversed_rec); // 输出相同结果 } ``` #### **关键实现技巧** 1. **指针操作三要素**：始终维护 `prev`、`curr`、`next` 三个指针 2. **头节点处理**：迭代法最终返回 `prev`（原尾节点变为头节点）[^4] 3. **递归终止条件**：`if (!head || !head->next)` 覆盖空链表和单节点情况 4. **内存安全**： - 迭代法适用于长链表（避免栈溢出） - 实际工程中推荐使用智能指针管理节点内存 --- ### 链表反转可视化示例 **原始链表**： `head → ① → ② → ③ → ∅` **迭代法步骤**： ``` Step1: ∅ ← ① ② → ③ → ∅ Step2: ∅ ← ① ← ② ③ → ∅ Step3: ∅ ← ① ← ② ← ③ [^1] ``` ---