常平镇仿做网站,网店代运营服务,徐州网站开发,怎么做单页网站导航原题链接#x1f517;#xff1a;反转链表 难度#xff1a;简单⭐️
题目
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5] 输出#xff1a;[5,4,3,2,1]
示例 2#xff1a;…原题链接反转链表 难度简单⭐️
题目
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 1 输入head [1,2,3,4,5] 输出[5,4,3,2,1]
示例 2
输入head [1,2] 输出[2,1]
示例 3 输入head [] 输出[]
提示
链表中节点的数目范围是 [0, 5000] -5000 Node.val 5000
进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题
题解
迭代法
题解 有两种常见的方法来解决这个问题迭代和递归。 迭代方法 初始化三个指针prev 初始化为 nullptr因为反转后的链表第一个节点的 next 应该是nullptrcurrent 初始化为头节点 headnext 用于临时存储下一个节点。遍历链表使用一个循环当 current 不为 nullptr 时执行以下操作 保存 current 的下一个节点到 next。将 current 的 next 指向 prev实现反转。更新 prev 和 current 为下一个节点prev currentcurrent next。 当循环结束时prev 将指向反转后的头节点返回 prev。 递归方法 基本情况如果 head 是 nullptr 或者 head-next 是 nullptr说明链表为空或只有一个节点直接返回 head。递归反转递归调用 reverseList 函数传入 head-next 作为参数获取反转后的链表的头节点。重新链接节点将当前节点 head 的下一个节点的 next 指向 head实现反转。设置当前节点的 next 为 nullptr防止链表形成环。返回新的头节点递归调用返回的头节点。 复杂度时间复杂度O(n)空间复杂度O(1)。过程迭代法如下代码。c demo
#include iostream// 定义链表节点
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 解决方案类
class Solution {
public:// 迭代方法反转链表ListNode* reverseList(ListNode* head) {ListNode* prev nullptr;ListNode* current head;ListNode* next nullptr;while (current ! nullptr) {next current-next; // 保存下一个节点current-next prev; // 反转当前节点的指针prev current; // 移动prev到当前节点current next; // 移动current到下一个节点}return prev; // 返回新的头节点}
};// 主函数用于演示
int main() {Solution solution;// 创建一个示例链表: 1 - 2 - 3 - 4 - 5ListNode* 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);// 打印原始链表std::cout Original List: ;ListNode* current head;while (current ! nullptr) {std::cout current-val - ;current current-next;}std::cout nullptr std::endl;// 反转链表ListNode* reversedHead solution.reverseList(head);// 打印反转后的链表std::cout Reversed List: ;current reversedHead;while (current ! nullptr) {std::cout current-val - ;current current-next;}std::cout nullptr std::endl;// 释放链表内存while (reversedHead ! nullptr) {ListNode* tmp reversedHead;reversedHead reversedHead-next;delete tmp;}return 0;
}输出结果 Original List: 1 - 2 - 3 - 4 - 5 - nullptr Reversed List: 5 - 4 - 3 - 2 - 1 - nullptr
