链表反转

c/c++蓝桥杯经典编程题100道-目录-CSDN博客

---

目录

链表反转

一、题型解释

二、例题问题描述

三、C语言实现

解法1：迭代反转（难度★）

解法2：递归反转（难度★★）

解法3：分组反转（难度★★★）

四、C++实现

解法1：迭代反转（难度★）

解法2：使用STL容器辅助（难度★★）

五、总结对比表

六、特殊方法与内置函数补充

1. C++智能指针

2. 链表调试技巧

---

一、题型解释

链表反转是将链表节点的连接方向完全逆序的操作。常见题型：

1. 基础反转：反转整个单链表（如 1→2→3→4→5 转为 5→4→3→2→1）。

2. 部分反转：反转链表的某个区间（如反转第2到第4个节点）。

3. 分组反转：每k个节点为一组进行反转（如k=2时，1→2→3→4→5 转为 2→1→4→3→5）。

4. 递归反转：用递归思想实现链表反转。

---

二、例题问题描述

例题1：输入链表 1→2→3→4→5，输出反转后的链表 5→4→3→2→1。
例题2：输入链表 1→2→3→4→5 和区间 [2,4]，输出 1→4→3→2→5。
例题3：输入链表 1→2→3→4→5 和k=2，输出 2→1→4→3→5。
例题4：输入链表 1→2，输出 2→1。

---

三、C语言实现

解法1：迭代反转（难度★）

通俗解释：

• 像翻书一样，逐个节点改变指针方向，将当前节点的next指向前一个节点。

c

#include <stdio.h>
#include <stdlib.h>struct ListNode {int val;struct ListNode *next;
};// 迭代反转链表
struct ListNode* reverseList(struct ListNode* head) {struct ListNode *prev = NULL, *curr = head;while (curr != NULL) {struct ListNode *nextTemp = curr->next; // 保存下一个节点curr->next = prev; // 当前节点指向前一个节点prev = curr;       // 前一个节点后移curr = nextTemp;   // 当前节点后移}return prev; // prev最终指向新链表的头节点
}// 打印链表
void printList(struct ListNode* head) {while (head != NULL) {printf("%d→", head->val);head = head->next;}printf("NULL\n");
}int main() {// 构建链表 1→2→3→4→5struct ListNode node5 = {5, NULL};struct ListNode node4 = {4, &node5};struct ListNode node3 = {3, &node4};struct ListNode node2 = {2, &node3};struct ListNode node1 = {1, &node2};struct ListNode* newHead = reverseList(&node1);printList(newHead); // 输出 5→4→3→2→1→NULLreturn 0;
}

代码逻辑：

1. 初始化指针：prev（前一个节点）初始为NULL，curr（当前节点）初始为头节点。

2. 循环操作：

   • 保存下一个节点 nextTemp = curr->next。

   • 将当前节点的 next 指向 prev。

   • prev 和 curr 向后移动。

3. 终止条件：当 curr 为NULL时，prev 成为新链表的头节点。

---

解法2：递归反转（难度★★）

通俗解释：

• 假设后面的链表已经反转，只需处理当前节点和已反转部分的连接。

c

struct ListNode* reverseListRecursive(struct ListNode* head) {if (head == NULL || head->next == NULL) {return head; // 基线条件：空链表或只剩一个节点}struct ListNode* newHead = reverseListRecursive(head->next); // 递归反转后续链表head->next->next = head; // 当前节点的下一个节点指向自己（反转方向）head->next = NULL;       // 断开原有连接return newHead; // 返回新头节点
}int main() {// 测试递归反转struct ListNode* newHead = reverseListRecursive(&node1);printList(newHead); // 输出 5→4→3→2→1→NULLreturn 0;
}

代码逻辑：

1. 基线条件：链表为空或只剩一个节点时直接返回。

2. 递归调用：先反转 head->next 之后的链表，得到新头节点 newHead。

3. 反转当前节点：将当前节点的下一个节点的 next 指向自己，再断开自己的 next。

4. 递归栈展开：从最后一个节点开始逐层反转。

---

解法3：分组反转（难度★★★）

通俗解释：

• 每k个节点为一组，组内反转，若剩余节点不足k个则保持原顺序。

c

struct ListNode* reverseKGroup(struct ListNode* head, int k) {struct ListNode *curr = head;int count = 0;// 检查是否足够k个节点while (curr != NULL && count < k) {curr = curr->next;count++;}if (count == k) { // 足够k个节点时反转struct ListNode *prev = reverseKGroup(curr, k); // 递归处理后续分组// 反转当前k个节点while (count-- > 0) {struct ListNode *nextTemp = head->next;head->next = prev;prev = head;head = nextTemp;}head = prev;}return head; // 不足k个时直接返回原头节点
}int main() {// 测试分组反转（k=2）struct ListNode* newHead = reverseKGroup(&node1, 2);printList(newHead); // 输出 2→1→4→3→5→NULLreturn 0;
}

代码逻辑：

1. 检查分组长度：遍历链表，判断剩余节点是否足够k个。

2. 递归处理后续分组：若足够，递归反转后续链表，返回已反转部分的头节点。

3. 反转当前分组：用迭代法反转当前k个节点，连接到已反转部分。

4. 终止条件：若不足k个，直接返回当前头节点。

---

四、C++实现

解法1：迭代反转（难度★）

通俗解释：

• 与C语言迭代法逻辑相同，使用指针操作。

cpp

#include <iostream>
using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *prev = NULL, *curr = head;while (curr != NULL) {ListNode *nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;}
};int main() {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);Solution sol;ListNode *newHead = sol.reverseList(head);while (newHead != NULL) {cout << newHead->val << "→";newHead = newHead->next;}cout << "NULL" << endl; // 输出 5→4→3→2→1→NULLreturn 0;
}

代码逻辑：

• 与C语言版本完全一致，但使用C++的类和对象封装。

---

解法2：使用STL容器辅助（难度★★）

通俗解释：

• 将链表存入容器（如栈或数组），反向构建新链表。

cpp

ListNode* reverseListSTL(ListNode* head) {vector<int> values;ListNode *curr = head;while (curr != NULL) { // 存入数组values.push_back(curr->val);curr = curr->next;}ListNode *dummy = new ListNode(0);curr = dummy;for (int i = values.size() - 1; i >= 0; i--) { // 反向遍历数组curr->next = new ListNode(values[i]);curr = curr->next;}return dummy->next;
}int main() {ListNode *head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);ListNode *newHead = reverseListSTL(head);// 输出 3→2→1→NULLreturn 0;
}

代码逻辑：

1. 存储节点值：遍历链表，将节点的值存入数组。

2. 反向构建链表：从数组末尾开始遍历，创建新节点并连接。

3. 优点：代码简单，但空间复杂度为O(n)。

---

五、总结对比表

方法	时间复杂度	空间复杂度	优点	缺点
迭代反转	O(n)	O(1)	高效，无需额外空间	需处理多个指针
递归反转	O(n)	O(n)	代码简洁	栈空间消耗大
分组反转	O(n)	O(1)	支持复杂需求	实现较复杂
STL容器辅助	O(n)	O(n)	代码简单	空间效率低

---

六、特殊方法与内置函数补充

1. C++智能指针

• 作用：自动管理内存，避免内存泄漏（需包含 <memory> 头文件）。

• 示例：

  shared_ptr<ListNode> node = make_shared<ListNode>(1);

2. 链表调试技巧

• 打印链表：编写打印函数时，可在每个节点后添加箭头（→），末尾标记 NULL。

• 图形化工具：使用在线数据结构可视化工具（如VisuAlgo）辅助调试。

c/c++蓝桥杯经典编程题100道-目录-CSDN博客