【Leetcode -86.分隔链表 -92.反转链表Ⅱ】
Leetcode
- Leetcode -86.分隔链表
- Leetcode -92.反转链表Ⅱ
Leetcode -86.分隔链表
题目:给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1:
输入:head = [1, 4, 3, 2, 5, 2], x = 3
输出:[1, 2, 2, 4, 3, 5]
示例 2:
输入:head = [2, 1], x = 2
输出:[1, 2]
我们的思路是,遍历链表的每个元素,如果比x小则拿下来放到一个small的结构体指针中;否则,放到一个large的指针中;最后,判断small是否为空,如果为空,则说明链表中的元素全都是比x大或等于x;否则,链表中的元素有比x大或等于,也有比x小的,这时候将small的尾部接到large上即可;
struct ListNode* partition(struct ListNode* head, int x){//small放比x小的值//large放大于等于x的值//smalltail和largetail分别是它们的尾struct ListNode* large = NULL, * small = NULL;struct ListNode* largetail = NULL, * smalltail = NULL;//从头开始遍历,到空结束while (head){//head的val比x小,放到smallif (head->val < x){//当small为空,即没有值的时候,small和smalltail都更新为当前的head//head迭代往后走,尾的next置空if (small == NULL){small = smalltail = head;head = head->next;smalltail->next = NULL;}//否则,更新尾并迭代head即可else{smalltail->next = head;head = head->next;smalltail = smalltail->next;smalltail->next = NULL;}}//当head的val比x大或等于x,与上面类似else{if (large == NULL){large = largetail = head;head = head->next;largetail->next = NULL;}else{largetail->next = head;head = head->next;largetail = largetail->next;largetail->next = NULL;}}}//如果链表中的值有大有小,即small这个链表不为空,就将small尾部的next接到large,然后再返回smallif (small)smalltail->next = large;//这种情况则是链表中的值全都大于或等于x,直接返回large即可elsereturn large;return small;}
Leetcode -92.反转链表Ⅱ
题目:给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。
请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
示例 1:
输入:head = [1, 2, 3, 4, 5], left = 2, right = 4
输出:[1, 4, 3, 2, 5]
示例 2:
输入:head = [5], left = 1, right = 1
输出:[5]
我们的思路是,使用leftcur和rightcur指针走到链表中left位置和right位置,反转left位置到right位置即可;当left为1,即在头节点的位置时,最终只需要返回反转后的链表;当left不在头节点的位置,我们用一个指针cur记录leftcur的前一个位置,我们只需要将cur->next 接到反转后的链表,并返回头节点即可;
当left = 1,right = 3:


反转后整理的链表,返回prev即可,即返回反转后的链表;

当left不为1,left = 2,right = 3:

在函数中反转后的链表如下两个图,所以需要将原链表中cur->next接到反转后的链表中,再返回head;


代码以及注释:
struct ListNode* Reverse(struct ListNode* prev, struct ListNode* dest){struct ListNode* curr = prev->next;prev->next = dest->next;while (prev != dest){struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}struct ListNode* reverseBetween(struct ListNode* head, int left, int right){//当左下标和右下标相同,不需要反转,返回headif (left == right)return head;struct ListNode* cur = head;struct ListNode* leftcur = head, * rightcur = head;//leftcur走到链表中left的位置while (--left){leftcur = leftcur->next;}//rightcur走到链表中right的位置while (--right){rightcur = rightcur->next;}//cur从头遍历,当cur等于leftcur或者cur->next等于leftcur时停下while (cur != leftcur && cur->next != leftcur){cur = cur->next;}//cur->next等于leftcur,反转leftcur到rightcur长度的链表//并且将cur的next接到反转后的链表去//返回头节点if (cur != leftcur){cur->next = Reverse(leftcur, rightcur);return head;}//cur等于leftcur,即cur = leftcur = head,//就反转leftcur到rightcur长度的链表,返回反转后的链表即可else{return Reverse(leftcur, rightcur);}}
相关文章:
【Leetcode -86.分隔链表 -92.反转链表Ⅱ】
Leetcode Leetcode -86.分隔链表Leetcode -92.反转链表Ⅱ Leetcode -86.分隔链表 题目:给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每…...
算法记录 | 48 动态规划
198.打家劫舍 思路: 1.确定dp数组(dp table)以及下标的含义:dp[i]:前 i 间房屋所能偷窃到的最高金额。 2.确定递推公式:dp[i] max(dp[i - 2] nums[i-1], dp[i - 1]) i间房屋的最后一个房子是nums[i−…...
CRM部署Always on 后 CRM报无法更新数据库,数据库只读,且读写分离不正常
CRM部署Always on 后 CRM报无法更新数据库,数据库只读,读写分离不正常 问题描述背景信息问题原因解决方案 问题描述 CRM部署Always on 后 CRM报无法更新数据库,数据库只读 读写分离不正常,出现错乱链接。 背景信息 1.2个节点配置SQL serve…...
麓言信息设计创意思维,打开设计师思路
在现在快速发展的时代,信息纷杂繁琐,如果一个设计不能让人眼前一亮,印象深刻,只会沦为平凡作品,无亮点无用处。正所谓,无设计不创意,这句口号正是喊出对设计的要求。 伴随着时代的发展、…...
POJ3704 括号匹配问题 递归方法
目录 题目 算法 完整代码 题目 参考 递归: https://blog.csdn.net/qq_45272251/article/details/103257953 利用了递归, 但思路稍复杂了 循环: https://blog.csdn.net/weixin_50340097/article/details/114579805 (看起来是递归其实是循环. 每次递归其实是循环内一次迭…...
leetcode — JavaScript专题(三):完全相等的 JSON 字符串、复合函数、 分组、柯里化、将对象转换为 JSON 字符串
专栏声明:只求用最简单的,容易理解的方法通过,不求优化,不喜勿喷 2628. 完全相等的 JSON 字符串 题面 给定两个对象 o1 和 o2 ,请你检查它们是否 完全相等 。 对于两个 完全相等 的对象,它们必须包含相…...
OGNL 的表达式
目录 概念 基本原理 基本语法 1、访问Root区域对象基本语法 2、访问Context区域对象基本语法 符号含义 概念 Object-Graph Navigation Language 对象-图形导航语言, 主要用于访问对象的数据和方法。 基本原理 主要由3部分构成:1.OGNL引擎 …...
JAVA面试中遇到的那些坑,80%的人都种过招
面试,是很多学完Java开发的人不得不面对的问题。小编经常听到学员抱怨,明明觉得自己学的不错,为什么到了面试的时候就凉凉了?为什么有的面试官会一直问业务层面的问题,让人措手不及? 其实,我们在学习Java知识的同时…...
【测试开发】单元测试、基准测试和性能分析(以 Go testing 为例)
一、为什么需要测试🤔️ 你写不出 bug-free 的代码。你认为自己写出了 bug-free 的代码,但它在你意想不到的地方出错了。你觉得自己写出了永不出错的代码,但它的性能十分糟糕。 二、在开发过程中做好测试(理想情况下)…...
linux中一条命令查询当前端口的进程,然后拿到进程pid,作为另一条杀死进程的参数
1. 可以使用lsof命令来查询端口对应的进程,然后使用awk命令提取PID,最后将其作为另一条命令的参数。 例如,如果要查询端口为8080的进程: lsof -i :8080 | awk NR2{print $2}其中,-i选项指定查询网络连接,…...
程序员找工作难吗?我用亲身经历来告诉大家
我看到很多同学说今年的程序员找工作难。我的心里也有一定预期,但直到我出来之后才真正地感受到这股寒冬有多么凛冽。 一个外包公司有四五个招聘人员,然后外包公司有十来个,一个公司的岗位会分发给这些各个不同的外包公司。所以你看到我沟通…...
【Web服务】HTTP和DNS重要知识
304状态码 HTTP状态码中的304状态码表示"未修改",通常在客户端发起了一个带有If-Modified-Since头部的GET请求时会得到这个响应。服务器通过比较If-Modified-Since头部指定的时间戳和资源的最后修改时间来判断资源是否被修改过,如果没有修改则…...
【C++】-关于类和对象的默认成员函数(中)-拷贝构造函数和赋值运算符重载函数
💖作者:小树苗渴望变成参天大树 ❤️🩹作者宣言:认真写好每一篇博客 💨作者gitee:gitee 💞作者专栏:C语言,数据结构初阶,Linux,C 如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点…...
c++11上篇
c11 1.C11简介2.列表初始化2.1 {}初始化2.2 std::initializer_list 3.变量类型推导3.1 auto3.2 decltype3.3 nullptr 4.范围for循环5.final与override6.智能指针7.新增加容器---静态数组array、forward_list以及unordered系列8.默认成员函数控制9.右值引…...
异构无线传感器网络路由算法研究(Matlab代码实现)
目录 💥1 概述 📚2 运行结果 🎉3 参考文献 👨💻4 Matlab代码 💥1 概述 无线传感器网络(Wireless Sensor Networks, WSN)是一种新型的融合传感器、计算机、通信等多学科的信息获取和处理技术的网络,…...
MySQL数据库——MySQL TRUNCATE:清空表记录
MySQL 提供了 DELETE 和 TRUNCATE 关键字来删除表中的数据。下面主要讲解一下 TRUNCATE 关键字的使用。 TRUNCATE 关键字用于完全清空一个表。其语法格式如下: TRUNCATE [TABLE] 表名 其中,TABLE 关键字可省略。 例 1 新建表 tb_student_course&…...
财报解读:连续三年逆势增长的背后,欧派家居到底靠的是什么?
能在过去3年逆势增长的家居企业并不多,而欧派家居就是其中一个。4月25日,欧派家居发布2022年年度报告。据年报数据显示,2022年,欧派家居共实现营业收入224.80亿元,净利润约26.88亿元。 从2020年到2022年,欧…...
希望计算机专业同学都知道这些宝藏博主
湖科大教书匠——计算机网络 “宝藏老师”、“干货满满”、“羡慕湖科大”…这些都是网友对这门网课的评价,可见网课质量之高! 湖南科技大学《计算机网络》微课堂是该校高军老师精心制作的视频课程,用简单的语言描述复杂的问题,…...
1694_week1_MIT使用Python编程学习手记1
全部学习汇总: GreyZhang/python_basic: My learning notes about python. (github.com) 首先说明一下,这部分信息的整理只是我个人的理解。由于自己的知识功底以及英语水准,很可能会有大量的疏漏。再此,我只想把自己学习时候的一…...
第二十一章 光源
光源是每个场景必不可少的部分,光源除了能够照亮场景之外,还可以产生阴影效果。 Unity中分为四种光源类型: 1. 方向光:Directional Light 用于模拟太阳光,方向光任何地方都能照射到。 2. 点光源:Point L…...
AI算法Excel可视化终极指南:如何用电子表格深度解析人工智能原理
AI算法Excel可视化终极指南:如何用电子表格深度解析人工智能原理 【免费下载链接】ai-by-hand-excel 项目地址: https://gitcode.com/gh_mirrors/ai/ai-by-hand-excel 你是否曾被复杂的AI算法公式和抽象概念困扰,想要找到一种更直观的学习方式&a…...
DLL与静态库怎么选?5个真实案例解析动态链接库的优劣
DLL与静态库的架构决策:5个实战场景下的技术选型指南 1. 模块化开发中的DLL实践 在大型软件系统中,模块化设计是降低复杂度的关键策略。我们曾为某金融交易系统设计插件架构时,DLL的动态加载特性展现出独特优势: 内存共享机制&…...
基于LLM的智能客服系统实战:飞书集成与高并发架构设计
最近在做一个企业级的智能客服项目,客户要求必须集成到飞书工作台,并且要能扛住业务高峰期的并发压力。传统的规则引擎客服系统,在面对五花八门的用户提问时,经常“卡壳”,尤其是那些规则库没覆盖到的“长尾问题”&…...
Wireshark 实战|HTTP 协议:浏览器和服务器是怎么聊天的?
Wireshark 实战|HTTP 协议:浏览器和服务器是怎么聊天的? 大家好,我是网域小星球,一名网络工程大三学生。上一篇我们拆解了 DNS 域名解析,今天我们继续往下走,看看拿到 IP 地址后,浏…...
Cosmos-Reason1-7B保姆级教程:从NVIDIA模型下载到浏览器界面可用全流程
Cosmos-Reason1-7B保姆级教程:从NVIDIA模型下载到浏览器界面可用全流程 本文面向想要快速上手Cosmos-Reason1-7B推理工具的初学者,无需深厚技术背景,跟着步骤操作即可完成本地部署和使用。 1. 工具简介:你的本地推理助手 Cosmos-…...
免费降AI率和付费降AI率差距有多大?降论文ai率效果实测对比
免费降AI率和付费降AI率差距有多大?降论文ai率效果实测对比 “有没有免费的降AI率工具?” 这是毕业季被问得最多的问题之一。毕竟论文查重已经花了一笔钱,再加上降AI率的费用,对学生来说确实是一笔不小的开支。 但免费降AI率方案真…...
Python金融计算提速迫在眉睫!(仅剩3类未公开的底层优化手段,第3种已被高盛2023年专利覆盖)
第一章:Python金融计算提速迫在眉睫!(仅剩3类未公开的底层优化手段,第3种已被高盛2023年专利覆盖)高频回测、实时风险敞口计算与蒙特卡洛期权定价正面临Python原生执行效率的严峻瓶颈。当单次万标的风险因子矩阵运算耗…...
3项突破重构浏览体验:从卡顿到丝滑的技术革命
3项突破重构浏览体验:从卡顿到丝滑的技术革命 【免费下载链接】thorium Chromium fork named after radioactive element No. 90. Windows and MacOS/Raspi/Android/Special builds are in different repositories, links are towards the top of the README.md. …...
VMware安装RHEL9连接Xshell与Linux基础命令vim练习
1、在VMware上创建虚拟机以及安装RHEL9操作系统,使用ssh进行远程连接2、文件管理命令练习: 1(1)在/opt目录下创建一个临时目录tmp;2(2)在临时目录下创建一个文件,文件名为a.txt;3、vi/vim练习:完成如下步骤(1)应用vi命令在/tmp文件夹下创建文…...
从Autoencoder到VAE:探索生成模型的演进之路
1. 从数据压缩到生成模型:Autoencoder的诞生 2006年,当Geoffrey Hinton团队首次提出Autoencoder(自编码器)时,这个看似简单的神经网络结构悄然打开了深度学习的新篇章。想象一下你正在整理杂乱的书架——先把书籍按主题…...
