反转链表、链表内指定区间反转

反转链表

给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。

如当输入链表{1,2,3}时,经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。以上转换过程如下图所示:

在这里插入图片描述
示例:

输入:{1,2,3}
返回值:{3,2,1}

好久好久没有刷题了,这一年大多在写Shell脚本或者Python脚本去了,已经忘记自己是C++起家的了,好几天前大页表吴同学找了两个题目说有意思让我试一下,害,当天晚上没做出来,有时间了再看这题目,其实就是头插法,尾插法是正序,头插法就是反转了,代码附上,关键是第二题。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <cstddef>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;}
};

链表内指定区间反转

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转。
在这里插入图片描述
这个题目首先我的想法就是把第一题反转的函数用上,然后把只需要截断反转再连接就可以了。我们使用示例{1,2,3,4,5},2,4。

第一种思路:

首先是找到需要反转的区间链表,

ListNode* dummyNode = new ListNode(-1);
dummyNode->next = head;ListNode* pre = dummyNode;
for(int i=0;i<m-1;i++){pre = pre->next;
}ListNode* rightNode = pre ;
for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;
}ListNode* leftNode = pre->next;//leftNode = {2,3,4,5}
ListNode* cur = rightNode->next;//后置链表 cur = {5}//截断链表
pre->next=NULL;//前置链表截断 pre = {1}
rightNode->next=NULL;//后置链表截断 leftNode = {2,3,4}

反转函数:

ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;
}

得到反转后的区间后,前置部分直接链接,后置部分通过遍历到反转区间链表的最后一个元素指向最后一部分。

ListNode* mid = ReverseList(leftNode);//mid = {4,3,2}pre->next = mid;
while (mid ->next)mid = mid -> next;
mid ->next = cur;
return dummyNode->next;

完整代码:

/*** struct ListNode {*  int val;*  struct ListNode *next;*  ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <ios>
#include <iostream>
using namespace std;
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param head ListNode类* @param m int整型* @param n int整型* @return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}return Rs;}ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* pre = dummyNode;for(int i=0;i<m-1;i++){pre = pre->next;}ListNode* rightNode = pre ;for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;}ListNode* leftNode = pre->next;ListNode* cur = rightNode->next;pre->next=NULL;rightNode->next=NULL;ListNode* mid = ReverseList(leftNode);pre->next = mid;while (mid ->next)mid = mid -> next;mid ->next = cur;return dummyNode->next;}
};

第二种思路:

第二种思路就是反转函数返回一个链表有点多此一举,只需要在反转函数里对链表进行操作即可。
反转函数:

void ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}
}

反转后:

//反转前 leftNode = {2,3,4} rightNode = {4}
ReverseList(leftNode);
//反转后 leftNode = {2} rightNode = {4,3,2}
pre->next = rightNode;
leftNode->next = cur;
return dummyNode->next;

完整代码:

/*** struct ListNode {*  int val;*  struct ListNode *next;*  ListNode(int x) : val(x), next(nullptr) {}* };*/
#include <ios>
#include <iostream>
using namespace std;
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param head ListNode类* @param m int整型* @param n int整型* @return ListNode类*/void ReverseList(ListNode* head) {// write code hereListNode* Rs = NULL;ListNode* Next = head->next;ListNode* Cur = head;while(Cur){Cur->next = Rs;Rs = Cur;Cur = Next;Next = Next->next;}}ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* pre = dummyNode;for(int i=0;i<m-1;i++){pre = pre->next;}ListNode* rightNode = pre ;for(int i=0;i<n-m+1;i++){rightNode = rightNode->next;}ListNode* leftNode = pre->next;ListNode* cur = rightNode->next;pre->next=NULL;rightNode->next=NULL;ReverseList(leftNode);pre->next = rightNode;leftNode->next = cur;return dummyNode->next;}
};

链表介绍

链表(Linked List)是一种线性数据结构,其中的元素(通常称为节点)按顺序排列,每个节点包含两部分信息:存储数据的部分和指向下一个节点的指针或引用。链表中的每个节点通过指针连接在一起,因此它不需要在内存中连续存储。链表有几种常见的形式:

  • 单向链表(Singly Linked List):每个节点只包含一个指向下一个节点的指针,链表是单向的,无法向后遍历。
  • 双向链表(Doubly Linked List):每个节点包含两个指针,一个指向下一个节点,另一个指向前一个节点,因此可以双向遍历。
  • 循环链表(Circular Linked List):链表的最后一个节点指向链表的第一个节点,形成一个环。

链表的优点:

  • 动态内存分配:链表不需要预先定义大小,可以根据需要动态增长或缩小。

  • 插入和删除操作:链表的插入和删除操作可以在常数时间内完成,特别是对于已知位置的节点。
    链表的缺点:

  • 随机访问:由于链表的元素不在连续的内存位置,因此不能像数组一样通过索引进行随机访问,必须从头节点开始遍历。

链表广泛应用于实现队列、栈以及某些复杂数据结构,如图和哈希表的底层实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/18408.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

SpringCloud篇(服务网关 - GateWay)

目录 一、简介 二、为什么需要网关 二、gateway快速入门 1. 创建gateway服务&#xff0c;引入依赖 2. 编写启动类 3. 编写基础配置和路由规则 4. 重启测试 5. 网关路由的流程图 6. 总结 三、断言工厂 四、过滤器工厂 1. 路由过滤器的种类 2. 请求头过滤器 3. 默认…

MATLAB实现历史模拟法计算VaR(Value at Risk)

MATLAB实现历史模拟法计算VaR(Value at Risk) 历史模拟法&#xff08;Historical Simulation Method&#xff09;是一种用于计算风险值&#xff08;Value at Risk, VaR&#xff09;的非参数方法。它基于过去的资产价格或收益数据来估计未来的潜在损失。 MATLAB代码如下: 完整…

数据结构——红黑树

目录 一.红黑树 二.红黑树的实现 1.红黑树节点的定义 2.红黑树的插入 3.红黑树的遍历 4.检测红黑树 5.红黑树的查找 6.红黑树的性能 三.整体代码 1.RBTree.h 2.RBTree.cpp 一.红黑树 1.红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上…

OMV7 树莓派 tf卡安装

​ 升级7之后&#xff0c;问题多多&#xff0c;不是docker不行了&#xff0c;就是代理不好使 今天又重装了一遍&#xff0c;用官方的链接&#xff0c;重新再折腾一遍…… 使用raspberry pi imager安装最新版lite OS。 注意是无桌面 Lite版 配置好树莓派初始化设置&#xff0…

Java集合ConcurrentHashMap——针对实习面试

目录 Java集合ConcurrentHashMapConcurrentHashMap的特性是什么&#xff1f;HashMap和ConcurrentHashMap的区别&#xff1f;说说ConcurrentHashMap的底层实现 Java集合ConcurrentHashMap ConcurrentHashMap的特性是什么&#xff1f; 线程安全性 多线程并发读写安全&#xff1a…

攻防世界-mfw

进入题目以后可以点击三个网页&#xff0c;这三个网页其中有一个提示我们git、php、Bootstrap。可以联想到是git泄露 在url后面的参数改为.git 存在git漏洞&#xff0c;这时候就可以利用python的githacker库下载泄漏的文件 查看index.php的源代码 <?phpif (isset($_GET[pa…

MySQL面试之底层架构与库表设计

华子目录 mysql的底层架构客户端连接服务端连接的本质&#xff0c;连接用完会立马丢弃吗解析器和优化器的作用sql执行前会发生什么客户端的连接池和服务端的连接池数据库的三范式 mysql的底层架构 客户端连接服务端 连接的本质&#xff0c;连接用完会立马丢弃吗 解析器和优化器…

代理(下):结构化工具对话、Self-Ask with Search以及Plan and execute代理

在上一讲中&#xff0c;我们深入LangChain程序内部机制&#xff0c;探索了AgentExecutor究竟是如何思考&#xff08;Thought&#xff09;、执行&#xff08;Execute/Act&#xff09;和观察&#xff08;Observe&#xff09;的&#xff0c;这些步骤之间的紧密联系就是代理在推理&…

RPC-路由策略

为什么选择路由策略&#xff1f; 每次上线应用的时候都不止一台服务器会运行实例&#xff0c;那上线就涉及到变更&#xff0c;只要变更就可能导致原本正常运行的程序出现异常&#xff0c;尤其是发生重大变动的时候&#xff0c;导致应用不稳定的因素就变得很多。 灰度发布应用…

ctf日常

8&#xff0c; [NISACTF 2022]easyssrf 跨目录读取 NSSCTF{c42d6e04-f7cb-4ac4-925b-efd9b90c76ff} 9&#xff0c; [SWPUCTF 2021 新生赛]hardrce <?php header("Content-Type:text/html;charsetutf-8"); error_reporting(0); highlight_file(__FILE__); if(is…

Linux笔记---调试工具GDB(gdb)

1. gdb的概念 GDB&#xff0c;全称GNU Debugger&#xff0c;是一个功能强大的开源调试工具&#xff0c;广泛用于Unix和类Unix系统&#xff0c;以及Microsoft Windows和macOS平台。GDB允许开发者在程序执行过程中查看内部运行情况&#xff0c;帮助定位和修复程序中的错误。 gd…

服务架构的演进:从单体到微服务的探索之旅

服务架构的演进&#xff1a;从单体到微服务的探索之旅 一 . 服务架构演变1.1 单体架构1.2 分布式架构1.3 微服务1.4 小结 二 . 微服务技术对比2.1 微服务系统架构图2.2 微服务技术对比2.3 企业需求 三 . Spring Cloud 随着企业业务的不断拓展和复杂度的提升&#xff0c;对软件系…

【论文笔记】LLaMA-VID: An Image is Worth 2 Tokens in Large Language Models

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: LLaMA-VID: An Image is W…

leetcode_二叉树最大深度

对二叉树的理解 对递归调用的理解 对内存分配的理解 基础数据结构&#xff08;C版本&#xff09; - 飞书云文档 每次函数的调用 都会进行一次新的栈内存分配 所以lmax和rmax的值不会混在一起 /*** Definition for a binary tree node.* struct TreeNode {* int val;* …

【模拟仿真】基于区间观测器的故障诊断与容错控制

摘要 本文提出了一种基于区间观测器的故障诊断与容错控制方法。该方法通过构建区间观测器&#xff0c;实现对系统状态的上下边界估计&#xff0c;从而在存在不确定性和外部噪声的情况下进行高效的故障诊断。进一步地&#xff0c;本文设计了一种容错控制策略&#xff0c;以保证…

Ubuntu24.04LTS在线安装Docker引擎

Ubuntu24.04LTS在线安装Docker引擎 文章目录 Ubuntu24.04LTS在线安装Docker引擎1. 官网教程2. 安装Docker引擎1. 卸载旧版本2. 使用存储库apt安装1. 设置Docker的APT仓库(官网)2. 设置Docker的APT仓库(阿里云-推荐) 3. 安装1. 安装最新版2. 安装指定的版本 1. 官网教程 官网安…

directed-map cache简单示例

这张图的地址映射是基于直接映射缓存的策略进行的&#xff0c;以下是详细解释&#xff1a; 直接映射缓存的映射方式 缓存块号 (Cache Block Number): 使用公式 Cache块号 主存块号 % 缓存块总数 来决定主存地址在哪个缓存块中存储。比如&#xff0c;这里 Cache块总数 4&#…

SpringBoot配置相关的内容

依赖Starter和Parent 查依赖坐标网站&#xff1a;Maven Repository: Search/Browse/Explorehttps://mvnrepository.com/ 设置配置文件 配置文件相关的配置 yml多个数据的书写 配置文件的读取

基于Python的仓库管理系统设计与实现

背景&#xff1a; 基于Python的仓库管理系统功能介绍 本仓库管理系统采用Python语言开发&#xff0c;利用Django框架和MySQL数据库&#xff0c;实现了高效、便捷的仓库管理功能。 用户管理&#xff1a; 支持员工和管理员角色的管理。 用户注册、登录和权限分配功能&#x…

使用tauri + naiveAdmin 构建桌面应用程序

非常好的如何部署naiveAdmin的文档笔记: 非常详细的 https://sx-code.github.io/wiki/adminpro/02_project_prepare/04_%E9%A1%B9%E7%9B%AE%E8%AE%BE%E7%BD%AE.html 阅读原码ing 前端框架 NaiveUiAdmin Rust 数据处理 ing … Mysql 数据库使用 ing …