【数据结构】第四站:单链表力扣题(一)
目录
一、移除链表元素
二、链表的中间结点
三、链表中倒数第k个结点
四、反转链表
五、合并两个有序链表
六、分割链表
一、移除链表元素
题目描述:力扣
法一:直接循环依次判断
对于这个题目,我们最容易想到的一种思路就是,直接遍历链表,当链表的值是需要删除的时候,直接删除即可,然后改变连接关系即可
代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* cur=head;struct ListNode* prev=NULL;while(cur!=NULL){if(cur->val!=val){prev=cur;cur=cur->next;}else {if(head==cur){head=cur->next;free(cur);cur=head;}else{struct ListNode* next=cur->next;free(cur);prev->next=next;cur=next;}}}return head; }对于我们写的这个代码,我们有以下几点需要注意:
1.当头结点就是需要删除的时候,那么prev是为空的,所以我们需要特殊处理,采用头删的思路即可。
2.这个函数传递的是一级指针,而非二级指针,原因是题目要求最后返回了头结点。所以可以不使用二级指针。
3.当代码出现问题,而在力扣上无法肉眼观察出错误的时候,我们就需要放到vs上进行调试,那么就涉及到需要自己手搓一个链表的问题,手搓的方法如下所示
int main() {struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));n1->val = 1;n2->val = 2;n3->val = 3;n4->val = 4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL; }
法二:尾插法
这个方法的思路是这样的,我们重新定义一个链表,这个链表使用两个结点指针来控制,一个是头节点newhead,另一个是尾结点tail。一开始让他们都为空,即这个链表是空链表
然后我们在使用一个结点指针cur来遍历原来的链表,如果此处的值不是val,那就将这个结点尾插到新链表上。然后让尾结点向后走,cur结点也向后走。注意当第一个结点插入的时候,由于tail为空,所以特殊处理,直接赋值,然后使cur向后走即可
如果某处的值确实是val,那么就要设置一个新结点next去接收cur的下一个结点,然后释放cur。然后让tail的下一个结点赋值为cur。注意,这里还有一个特殊情况是,当题目所给的链表全要被删除的时候,由于tail为空,所以无法让tail的下一个结点赋值为cur。这里我们直接使用一个if排除掉这种情况即可
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* newhead=NULL;struct ListNode* tail=NULL;struct ListNode* cur=head;while(cur!=NULL){if(cur->val!=val){if(newhead==NULL){newhead=cur;tail=cur;cur=cur->next;}else {tail->next=cur;tail=cur;cur=cur->next;}}else {struct ListNode* next=cur->next;free(cur);cur=next;if(tail!=NULL)tail->next=cur;}}return newhead; }
二、链表的中间结点
题目描述:力扣
解一:
对于这道题,我们最容易想到的思路就是,先遍历一遍,得到链表的长度,然后除2,就能得到要到达中间结点的长度。然后再一次遍历就能解出
解二:快慢指针
对于这道题,还有一种比较好的方法就是,一开始定义两个结点指针,然后一个一次走一步,另外一个一次走两步,如此一来,慢的那个指针恰好就是中间结点。具体代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast=head;struct ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow; }
三、链表中倒数第k个结点
题目链接:链表中倒数第k个结点_牛客题霸_牛客网
对于这道题目,与第二题十分相似,也是采用快慢指针的方式,不过不同的是,这里的快慢是距离的快慢,而上一道题是速度的快慢。
这道题目的关键就是,fast应该要先走k步,然后两者再一起走,当fast为空的时候,返回慢指针即可
如果fast先走k-1步,那么fast的下一个指针为空的时候,返回慢指针
注意如果链表为空,那么直接返回空即可,如果k大于链表长度,那么就直接返回空就可以,这就意味着,fast先走的时候,每走一步都要判断一下此时fast是否为空
/*** struct ListNode {* int val;* struct ListNode *next;* };*//*** * @param pListHead ListNode类 * @param k int整型 * @return ListNode类*/ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {if(pListHead==NULL){return NULL;}// write code herestruct ListNode* fast = pListHead;struct ListNode* slow = pListHead;while(k--){if(fast!=NULL)fast=fast->next;elsereturn NULL;}while(fast){fast=fast->next;slow=slow->next;}return slow; }
四、反转链表
题目描述:力扣
解一:直接改变指向
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode* prev=NULL;struct ListNode* cur=head;while(cur!=NULL){struct ListNode* next=cur->next;cur->next=prev;prev=cur;cur=next;}return prev; }如上代码所示,这是最容易想到的方法,直接改变指向,我们先定义三个指针,prev,cur和next,然后使用循环依次改变指向即可
解二:头插法
这个的思路跟前面的尾插法类似, 我们可以定义一个新的链表newhead,然后将原来链表的头一个一个取出来进行头插即可
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode* newhead=NULL;struct ListNode* cur=head;while(cur!=NULL){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead; }
五、合并两个有序链表
题目描述:力扣
解一:尾插法
这道题目也是比较适合尾插,如果第一个链表的数据小于第二个链表的数据,那么就尾插第一个,然后cur向后移动,反之也是一样的,代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* cur1=list1;struct ListNode* cur2=list2;struct ListNode* newhead=NULL;struct ListNode* tail=NULL;while(cur1&&cur2){if((cur1->val)<(cur2->val)){if(newhead==NULL){newhead=tail=list1;cur1=cur1->next;}else{tail->next=cur1;tail=cur1;cur1=cur1->next;}}else{if(newhead==NULL){newhead=tail=list2;cur2=cur2->next;}else{tail->next=cur2;tail=cur2;cur2=cur2->next;}}}if(cur1==NULL){tail->next=cur2;}else{tail->next=cur1;}return newhead; }
解二:哨兵位
我们可以先创建一个哨兵位,然后利用这个哨兵位去修改解法一的代码。可以一定程度上优化代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* cur1=list1;struct ListNode* cur2=list2;struct ListNode* guard=NULL;struct ListNode* tail=NULL;guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode));tail->next=NULL;while(cur1&&cur2){if((cur1->val)<(cur2->val)){tail->next=cur1;tail=cur1;cur1=cur1->next;}else{tail->next=cur2;tail=cur2;cur2=cur2->next;}}if(cur1==NULL){tail->next=cur2;}else{tail->next=cur1;}struct ListNode* head=guard->next;free(guard);guard=NULL;return head; }
六、分割链表
题目链接:力扣
解一:尾插法(不带哨兵位)
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* partition(struct ListNode* head, int x){struct ListNode* lesshead=NULL;struct ListNode* lesstail=NULL;struct ListNode* greaterhead=NULL;struct ListNode* greatertail=NULL;struct ListNode* cur=head;while(cur!=NULL){if(cur->val<x){//尾插到较小的链表if(lesshead==NULL){lesshead=lesstail=cur;cur=cur->next;}else{lesstail->next=cur;lesstail=cur;cur=cur->next;}}else{if(greaterhead==NULL){greaterhead=greatertail=cur;cur=cur->next;}else{greatertail->next=cur;greatertail=cur;cur=cur->next; }}}if(lesshead==NULL){return greaterhead;}if(greaterhead==NULL){return lesshead;}lesstail->next=greaterhead;greatertail->next=NULL;return lesshead; }对于这道题,依旧采取尾插法,既然要使用尾插法,那么势必需要构建两个新链表
题目要求是将所有小于x 的值全部放在前面,且不改变顺序
那么可以使用一个链表去管理小于x 的值。同样由于是尾插,需要使用头尾两个结点来管理
然后使用另外一个链表去管理大于等于x的值,也需要使用头尾两个结点去管理
由于是尾插,那么势必涉及到链表为空,这里的链表为空状态比较复杂。如果采用哨兵位的话,确实可以避免分情况讨论了。但是这里我们选择迎难而上,不采用哨兵位的解法
既然不采用哨兵位了,那么我们现在来分析这道题,首先是定义四个结点指针,然后我们去遍历原来的链表,如果小于x,尾插到较小链表,这里要注意,如果链表为空,需要分情况讨论。
如果大于等于x,尾插到较大链表,这里也要注意,如果链表为空,也需要分情况讨论
当尾插全部完成以后。
我们还需要进行分情况讨论,如果较小链表为空,那么直接返回较大链表即可,如果较大链表为空,返回较小链表即可。
然后我们链接较小链表和较大链表,最后要注意较大链表的尾部一定要置空,否则由于尾插可能会导致出现环。代码如上所示
解二:尾插法(带哨兵位)
前面我们已经知道了不带哨兵位的方法,我们发现,分情况讨论特别繁琐。对于尾插法,如果使用哨兵位,就可以直接无视掉所有的分情况讨论。而大体思路却不会变化太多,下面是代码。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* partition(struct ListNode* head, int x){struct ListNode* lessGuard=NULL;struct ListNode* lesstail=NULL;struct ListNode* greaterGuard=NULL;struct ListNode* greatertail=NULL;lessGuard=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));greaterGuard=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));greatertail->next=NULL;lesstail->next=NULL;struct ListNode* cur=head;while(cur!=NULL){if(cur->val<x){lesstail->next=cur;lesstail=cur;cur=cur->next;}else{greatertail->next=cur;greatertail=cur;cur=cur->next; }}lesstail->next=greaterGuard->next;greatertail->next=NULL;head=lessGuard->next;free(lessGuard);free(greaterGuard);lessGuard=greaterGuard=NULL;return head; }这里我们有一点需要特别注意,一定要让greatertail->next置为空,否则会陷入死循环,这也是使用哨兵位就需要做的一些细节,一旦使用哨兵位,一定要注意一些细节
本小节内容就到这里了,欲知后事请看下节
如果对你有帮助的话,一定要点赞加收藏哦!!!
相关文章:
【数据结构】第四站:单链表力扣题(一)
目录 一、移除链表元素 二、链表的中间结点 三、链表中倒数第k个结点 四、反转链表 五、合并两个有序链表 六、分割链表 一、移除链表元素 题目描述:力扣 法一:直接循环依次判断 对于这个题目,我们最容易想到的一种思路就是,…...
SAP BPC简介
BPC是SAP在financial application领域主推的产品,由于从原有产品线发展而来,产品本身有两个版本,分别是基于MS OLAP平台和Netweaver OLAP平台。 整个系统分为.net前台和abap后台。由于abap端的数据结构与.net数据结构的差异,所以没…...
Linux网络概述
写咋前面 今天,我们需要初步的认识一下Linux中网络的基本原理,只有大家对这个有一个初步的认识,后面我们学习起来才会更加的简单容易.计算机语言知识那么多,但是Linux不是.面试时,面试官总是会有问题难住你,我们后面需要看看书,这一点非常重要.我们现在谈的是脉络,.是框架.这些…...
Mybatis --- 获取参数值和查询功能
一、MyBatis的增删改查 1.1、新增 <!--int insertUser();--> <insert id"insertUser">insert into t_user values(null,admin,123456,23,男) </insert> 1.2、删除 <!--int deleteUser();--> <delete id"deleteUser">dele…...
【C++】C++入门,你必须要知道的知识
1.C关键字 🔥前言: C是在C的基础之上,容纳进去了面向对象编程思想,并增加了许多有用的库,以及编程范式等。熟悉C语言之后,对C学习有一定的帮助。今天的主要目标: 1️⃣ 补充C语言语法的不足&…...
spring(七):事务操作
spring(七):事务操作前言一、什么是事务二、事务四个特性(ACID)三、事务操作(搭建事务操作环境)四、事务操作(Spring 事务管理介绍)五、事务操作(注解声明式事…...
Word怎么转换成PDF文件格式?思路提供
PDF是一种通用的文件格式,它可以在不同操作系统和设备上保持一致的显示效果。在日常工作或学习中,我们常常需要将Word文档转换为PDF格式,以便更好地进行分享、存档或打印,毕竟Word文档则往往会因为不同版本的软件或者字体等原因而…...
HCIE-Cloud Computing LAB备考第二步:逐题攻破--第五题:规划--根据网络平面规划表,完成ensp中接入交换机SW1/2的配置
我是第五题规划题目的要求之一,需要从这里跳转过来,没看过题目的彭友,可以先跳转过去哈 解题:根据网络平面规划表,在两台交换机上对应的端口表填写服务器的网口号,完成ensp中接入交换机SW1/2的配置 答案 完成交换机端口表 第一:心中划分好“服务器接口表”,考试不需…...
【无标题】Perforce研讨会回顾 | Helix Core在芯片行业的应用实例:芯片项目的版本控制、持续集成及自动化
2023年2月28日,龙智联合全球领先的数字资产管理和DevSecOps工具厂商Perforce共同举办Perforce on Tour网络研讨会——“赋能‘大’研发,助力‘快’交付”。 研讨会上,在芯片行业有15年经验的Perforce Helix Core深度用户——何刚了带来精彩演…...
AdamW 优化器
Adam 优化器于 2014 年推出,其思想:既然知道某些参数移动得更快、更远,则每个参数不需要遵循相同的学习率,因为最近梯度的平方代表每一个权重可以得到多少信号,可以除以这个,确保即使是最迟钝的权重也有机会…...
手把手教你基于HTML、CSS搭建我的相册(上)
The sand accumulates to form a pagoda写在前面HTML是什么?CSS是什么?demo搭建写在最后写在前面 其实有过一些粉丝咨询前端该从什么开始学,那当然是我们的前端基础三件套开始学起,HTML、CSS、javaScript,前端的大部分…...
基于Redis实现的延时队列
基于Redis实现的延时队列 针对于Redis实现延时队列有两种实现方式: 使用zset实现实现的延时队列 借助redis zset来实现延时队列,具体的实现代码很简单,就是从zset中取出score小于当前时间戳的数据 import cn.hutool.json.JSONUtil; impor…...
(3.16——3.19)本周后半段总结
周四(3.16) 1.封装了TitleTip组件,并写了博客记录 http://t.csdn.cn/DAY4chttp://t.csdn.cn/DAY4c2.菜单跳转配置完毕,进行了一些页面的细节样式修改 3.基本写完了ServerSideEncryption页面,十一点多剩最后一点交互的…...
C++ 基础: cin和getline() 有啥区别?
所谓温故而知新,所以时不时会回头来看看我们最最基础的知识。 获取标准键盘输入的方法有多种。以C语言来说,最常用的就是cin 和geline() 。那么它们之间有什么区别呢,我们总结一下。 一、cin和geline的异同点 在 C 中,cin 和 ge…...
在使用fastjson中遇到的问题
一、在使用fastjson中遇到的问题 导论:最近在写一个JavaFx项目的时候使用到了fastjson作为处理json数据的依赖。在其它非JavaFx项目中也使用到了相同版本的fastjson,但是可以正常运行,而在JavaFx项目中却报异常,刚开始以为是我的依…...
C++造轮子飙车现场之无锁、有锁环形队列实现
先看带锁的实现。 带锁版本 circular_queue.h // 头文件防卫 #ifndef CIRCULAR_QUEUE_H #define CIRCULAR_QUEUE_H#include <mutex> // 互斥量 #include <condition_variable> // 条件变量template <typename T> class CircularQueue { public:// 构造函数…...
Spring Profiles and @Profile
1. Overview In this tutorial, we’ll focus on introducing Profiles in Spring. Profiles are a core feature of the framework — allowing us to map our beans to different profiles — for example, dev, test, and prod. We can then activate different profiles…...
数据分析-数据探索
文章目录前言主要内容总结更多宝藏前言 😎🥳😎🤠😮🤖🙈💭🍳🍱 随着大数据和人工智能技术的不断发展,数据分析已经成为了一种非常重要的技能和工…...
7个最受欢迎的Python库,大大提高开发效率
当第三方库可以帮我们完成需求时,就不要重复造轮子了 整理了GitHub上7个最受好评的Python库,将在你的开发之旅中提供帮助 PySnooper 很多时候时间都花在了Debug上,大多数人呢会在出错位置的附近使用print,打印某些变量的值 这个…...
Intellij IDEA 中调试 maven 插件
Intellij IDEA 中调试 maven 插件话痨一下步骤1. classfinal-demo 项目部分2. ClassFinal 部分参考资料话痨一下 目前有两个项目: ClassFinal 是一款java class文件安全加密工具。classfinal-demo 是我建的一个Demo,用来测试ClassFinal的加密效果。 目…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
