反转链表c++（反转链表C语言递归）

## 反转链表 C++### 简介链表反转是数据结构中一个经典的操作，也是面试中常见的算法题。它要求将一个链表的节点顺序颠倒，例如将 1->2->3->NULL 反转为 3->2->1->NULL。本文将详细介绍如何使用 C++ 实现链表反转。### 方法一：迭代法#### 1. 算法思路迭代法使用循环遍历链表，并将每个节点的指针指向其前一个节点，最终实现链表反转。#### 2. 代码实现```c++ #include // 定义链表节点结构体 struct ListNode {int val;ListNode

next;ListNode(int x) : val(x), next(nullptr) {} };// 反转链表 ListNode

reverseList(ListNode

head) {ListNode

prev = nullptr; // 指向前一个节点ListNode

curr = head; // 指向当前节点ListNode

next; // 指向下一个节点while (curr != nullptr) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针方向prev = curr; // 更新前一个节点curr = next; // 移动到下一个节点}return prev; // 返回反转后的链表头节点 }// 打印链表 void printList(ListNode

head) {while (head != nullptr) {std::cout << head->val << " ";head = head->next;}std::cout << std::endl; }int main() {// 创建链表 1->2->3->4->NULLListNode

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);head = reverseList(head); // 反转链表std::cout << "反转后的链表: ";printList(head);return 0; } ```#### 3. 代码解释- `prev`、`curr`、`next` 三个指针分别指向当前节点的前一个节点、当前节点和下一个节点，用于遍历链表和调整指针方向。 - 循环遍历链表，每次循环执行以下步骤：- 保存下一个节点 `next = curr->next`。- 反转当前节点的指针方向 `curr->next = prev`。- 更新前一个节点 `prev = curr`。- 移动到下一个节点 `curr = next`。 - 循环结束后，`prev` 指向反转后的链表头节点，返回 `prev`。### 方法二：递归法#### 1. 算法思路递归法利用函数调用栈的特性，递归地反转链表的子链表，并在回溯时将当前节点的指针指向其前一个节点。#### 2. 代码实现```c++ #include // 定义链表节点结构体 (同上)// 反转链表 ListNode

reverseListRecursive(ListNode

head) {if (head == nullptr || head->next == nullptr) {return head; // 递归终止条件}ListNode

newHead = reverseListRecursive(head->next); // 递归反转子链表head->next->next = head; // 反转当前节点指针方向head->next = nullptr; // 将当前节点的next指针设置为nullptrreturn newHead; // 返回反转后的链表头节点 }// 打印链表 (同上)int main() {// 创建链表 1->2->3->4->NULL (同上)std::cout << "原始链表: ";printList(head);head = reverseListRecursive(head); // 反转链表std::cout << "反转后的链表: ";printList(head);return 0; } ```#### 3. 代码解释- 递归函数 `reverseListRecursive` 接收链表头节点作为参数。 - 递归终止条件：如果链表为空或者只有一个节点，则直接返回头节点。 - 递归调用 `reverseListRecursive(head->next)` 反转子链表，并将返回值赋给 `newHead`。 - 在递归回溯时，将当前节点的 `next` 指针指向其前一个节点 (`head->next->next = head`)，并将当前节点的 `next` 指针设置为 `nullptr` (`head->next = nullptr`)。 - 返回 `newHead`，即反转后的链表头节点。### 总结本文介绍了两种常用的链表反转方法：迭代法和递归法。迭代法思路清晰，代码简洁易懂，而递归法则更加优雅，但对递归的理解要求较高。开发者可以根据实际情况选择合适的方法实现链表反转。

反转链表 C++

简介链表反转是数据结构中一个经典的操作，也是面试中常见的算法题。它要求将一个链表的节点顺序颠倒，例如将 1->2->3->NULL 反转为 3->2->1->NULL。本文将详细介绍如何使用 C++ 实现链表反转。

方法一：迭代法

1. 算法思路迭代法使用循环遍历链表，并将每个节点的指针指向其前一个节点，最终实现链表反转。

2. 代码实现```c++

include // 定义链表节点结构体 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {} };// 反转链表 ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr; // 指向前一个节点ListNode* curr = head; // 指向当前节点ListNode* next; // 指向下一个节点while (curr != nullptr) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针方向prev = curr; // 更新前一个节点curr = next; // 移动到下一个节点}return prev; // 返回反转后的链表头节点 }// 打印链表 void printList(ListNode* head) {while (head != nullptr) {std::cout << head->val << " ";head = head->next;}std::cout << std::endl; }int main() {// 创建链表 1->2->3->4->NULLListNode* 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);head = reverseList(head); // 反转链表std::cout << "反转后的链表: ";printList(head);return 0; } ```

3. 代码解释- `prev`、`curr`、`next` 三个指针分别指向当前节点的前一个节点、当前节点和下一个节点，用于遍历链表和调整指针方向。 - 循环遍历链表，每次循环执行以下步骤：- 保存下一个节点 `next = curr->next`。- 反转当前节点的指针方向 `curr->next = prev`。- 更新前一个节点 `prev = curr`。- 移动到下一个节点 `curr = next`。 - 循环结束后，`prev` 指向反转后的链表头节点，返回 `prev`。

方法二：递归法

1. 算法思路递归法利用函数调用栈的特性，递归地反转链表的子链表，并在回溯时将当前节点的指针指向其前一个节点。

2. 代码实现```c++

include // 定义链表节点结构体 (同上)// 反转链表 ListNode* reverseListRecursive(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head; // 递归终止条件}ListNode* newHead = reverseListRecursive(head->next); // 递归反转子链表head->next->next = head; // 反转当前节点指针方向head->next = nullptr; // 将当前节点的next指针设置为nullptrreturn newHead; // 返回反转后的链表头节点 }// 打印链表 (同上)int main() {// 创建链表 1->2->3->4->NULL (同上)std::cout << "原始链表: ";printList(head);head = reverseListRecursive(head); // 反转链表std::cout << "反转后的链表: ";printList(head);return 0; } ```

3. 代码解释- 递归函数 `reverseListRecursive` 接收链表头节点作为参数。 - 递归终止条件：如果链表为空或者只有一个节点，则直接返回头节点。 - 递归调用 `reverseListRecursive(head->next)` 反转子链表，并将返回值赋给 `newHead`。 - 在递归回溯时，将当前节点的 `next` 指针指向其前一个节点 (`head->next->next = head`)，并将当前节点的 `next` 指针设置为 `nullptr` (`head->next = nullptr`)。 - 返回 `newHead`，即反转后的链表头节点。

总结本文介绍了两种常用的链表反转方法：迭代法和递归法。迭代法思路清晰，代码简洁易懂，而递归法则更加优雅，但对递归的理解要求较高。开发者可以根据实际情况选择合适的方法实现链表反转。