力扣练习——链表在线OJ

目录

提示:

一、移除链表元素

题目:

解答:

二、反转链表

题目:

解答:

三、找到链表的中间结点

题目:

解答:

四、合并两个有序链表(经典)

题目:

解答:


提示:

①:接上一篇文章http://t.csdnimg.cn/vvmIr

本次我们来做一些在线OJ题,进一步加深印象和感觉,并且本次某些方法会沿用上一篇文章的,所以感兴趣的小伙伴可以参考一下上一篇文章。

②:对于这些在线OJ,小编会把具体步骤放在注释里面,然后小编没有画图,大家可自行画图然后跟着解析思路一起思考。

③:链表的在线OJ一般都是用的无哨兵的头指针,所以大家一定要搞懂有哨兵和无哨兵的区别。

一、移除链表元素

题目:

解答:

思路:只需要一边遍历链表,一边进行数据域的比较。若找到指定的值val,则删除该结点;

又因为删除一个结点,我们必须知道该结点的前一个结点,所以采用双指针的思路:

一个指针prve用于记录指定结点的前一个结点;

一个指针cur用于遍历寻找。

另外,找的过程中会发生两种情况;

情况一:指定结点为头结点(即头指针的位置):这时我们需要考虑头指针head的变化,具体实现看注释;

情况二:指定结点为一般结点:这时我们就依靠前一个结点正常删除即可;

源代码即注释如下:
 

struct ListNode* removeElements(struct ListNode* head, int val) 
{//双指针prev、curstruct ListNode* prev = NULL, *cur = head;//当cur==NULL。即过了尾结点,遍历完成,退出循环while (cur){//数据域相等,说明找到要删的结点if (cur->val == val){//分为两种情况,一是头删,二是正常删除if (cur == head)//头删{head = cur->next;free(cur);cur = head;}//正常删else{prev->next = cur->next;free(cur);cur = prev->next;}}//数据域不相同,则不是指定结点,向后走一步else{prev = cur;cur = cur->next;}}return head;
}

二、反转链表

题目:

解答:

思路:我们可以将当前结点的next域指向前一结点,但在此之前我们应该把当前结点的前一个结点和后一个结点给保存下来,防止结点丢失;

所以我们可以创建两个临时指针prve和cur;

cur用于保存下一个结点;

prve用于保存前一个结点;

而头结点head就用于保存当前结点;

struct ListNode* reverseList(struct ListNode* head) 
{//两个临时指针struct ListNode* cur = head, * prve = NULL;//因为cur是用于保存下一个结点,所以当cur为空时,即遍历完链表,循环结束while (cur){//cur保存下一个结点cur = cur->next;//将当前结点的next域指向前一个结点head->next = prve;//将prve保存当前结点,也就是保存下一轮操作的"前一个结点"prve = head;//完成一轮操作,head重定位当前结点head = cur;}//最后当head和cur都为NULL时,prve作为前一个结点即为"原链表的尾结点,反转链表的首结点”,所以返回prvereturn prve;
}

三、找到链表的中间结点

题目:

解答:

这道题用到一个经典思路叫:“快慢指针”;

即定义两个指针;

一个快指针fast,一次向后跳过两个结点;

一个慢指针slow,一次向后跳过一个结点;

初略想一下,当fast指针遍历完数组后,solw指针就是我们想要的中间结点;

但这里要分奇数个结点还是偶数个结点,如下:

奇数个结点的情况:

偶数个结点的情况:

所以结束有两个可能,即快指针指向尾结点或者快指针指向NULL;

struct ListNode* middleNode(struct ListNode* head) 
{//快指针fast,慢指针slowstruct ListNode* fast = head, * slow = head;//因为不确定奇数个还是偶数个,所以当快指针任意满足一种情况,则结束while (fast && fast->next){//慢指针走一步slow = slow->next;//快指针走两步fast = fast->next->next;}return slow;
}

四、合并两个有序链表(经典)

题目:

解答:

①:由合并升序链表,我们可以联想到合并升序顺序表(数组),我们知道是将大的一个数放在大空间的末尾,第二大的数放在大空间的倒数第二个位置,重复此操作,直到短的一方比较完,再把长的一方剩下的元素连接在末尾;

②:但链表和顺序表有一点区别是,链表只需要逻辑上相邻即可;

③:所以我们可以创建两个临时指针:

一个临时指针head用于充当新合并链表的头指针;

一个临时指针tail用于插入操作;

④:具体我们只需要将两个链表中的元素依次比较,再将数据域小的结点尾插到tail链表后面,因为tail和head指向同一个链表,只是head是头指针,过程中是tail再变,所以要注意tail指针的变化,最后返回head头指针即可。

⑤:其中我们可能遇到三种情况:

情况一、链表一或链表二为空,则直接返回另一个链表;

情况二、链表一和链表二长度相等,则循环上述操作;

情况三、长度不相等,则操作到某一时刻,链表一或二就会为NULL,这时就会出循环,然后再将长的链表剩下的元素插到tail结点后面。

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{//情况一、表一或表二为NULL,直接返回另一个表if (list1 == NULL)return list2;if (list2 == NULL)return list1;//情况二、按正常操作来进行struct ListNode* head = NULL, * tail = NULL;while (list1 && list2){//依次比较数据域if (list1->val < list2->val){//第一次需要将head和tail指针指向首结点较小的表,以便后续能尾插结点if (tail == NULL){head = tail = list1;}//尾插else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{//第一次需要将head和tail指针指向首结点较小的表,以便后续能尾插结点if (tail == NULL){head = tail = list2;}//尾插else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}//情况三、两个表长度不相等,会有一个表有剩余//因为是升序表,所以直接将剩余的表插入tail的next域即可if (list1){tail->next = list1;}if (list2){tail->next = list2;}//最后返回合并的表的头指针return head;
}

本次知识到此结束,希望对你有所帮助!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

opencv实现目标跟踪及视频转存

创建跟踪器 def createTypeTracker(trackerType): 读取视频第一帧&#xff0c;选择跟踪的目标 读第一帧。 ok, frame video.read() 选择边界框 bbox cv2.selectROI(frame, False) 初始化跟踪器 tracker_type ‘MIL’ tracker createTypeTracker(tracker_type) 用第一…

SpringBoot的全局异常拦截

在 Spring Boot 中&#xff0c;可以通过使用 ControllerAdvice 注解和 ExceptionHandler 注解来实现全局异常拦截。 RestControllerAdvice RestControllerAdvice 是 Spring Framework 提供的注解&#xff0c;用于定义全局异常处理类&#xff0c;并且结合 ExceptionHandler 注…

Rabbitmq安装-docker版

1.简介 2.安装消息队列 下载地址https://www.rabbitmq.com/download.html 使用docker方式安装 需要先下载docker&#xff0c;参考文章https://blog.csdn.net/weixin_43917045/article/details/104747341?csdn_share_tail%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22arti…

基于matlab创作简易表白代码

一、程序 以下是一个基于MATLAB的简单表白代码&#xff1a; % 表白代码 clc; % 清除命令行窗口 clear; % 清除所有变量 close all; % 关闭所有图形窗口 % 输入被表白者的名字 name input(请输入被表白者的名字&#xff1a;, s); % 显示表白信息 fprintf(\n); fprintf(亲爱的…

力扣刷题-哈希表-三数之和

15 三数之和 给你一个包含 n 个整数的数组 nums&#xff0c;判断 nums 中是否存在三个元素 a&#xff0c;b&#xff0c;c &#xff0c;使得 a b c 0 &#xff1f;请你找出所有满足条件且不重复的三元组。 注意&#xff1a; 答案中不可以包含重复的三元组。 示例&#xff1a…

由于计算机中丢失msvcp110.dll的解决方法与msvcp110.dll丢失修复方法

相信大家在打开电脑软件或许游戏都有遇到过电脑提示找不到msvcp110.dll文件&#xff0c;导致软件游戏打不开&#xff0c;我们应该怎么办&#xff1f;不用着急&#xff0c;今天小编我分享我找了很久成功解决问题的方法给大家&#xff0c;希望可以帮到各位。 1. 使用DLL修复工具&…

【word】从正文开始设置页码

在写报告的时候&#xff0c;会要求有封面和目录&#xff0c;各占一页。正文从第3页开始&#xff0c;页码从正文开始设置 word是新建的 分出三节&#xff08;封面、目录、正文&#xff09; 布局--->分割符--->分节符--->下一页 这样就能将word分为3节&#xff0c;分…

基于SSM的餐厅点菜管理系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用Vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

京东数据产品:8月大家电市场增长类目市场数据分析

上期我们已经分析了大家电市场及市场中的头部类目&#xff0c;从大家电的市场数据可知&#xff0c;整个行业大盘及多数细分市场都呈下滑走势。不过&#xff0c;仍有部分偏向精致生活的电器呈上升走势&#xff0c;如洗烘套装、内衣清洗机、衣物护理机等&#xff0c;下面我们一起…

案例突破——再探策略模式

再探设计模式 一、背景介绍二、 思路方案三、过程1. 策略模式基本概念2. 策略模式类图3. 策略模式基本代码策略类抽象策略类Context类客户端 4. 策略模式还可以进行优化的地方5. 对策略模式的优化&#xff08;配置文件反射&#xff09; 四、总结五、升华 一、背景介绍 在做项目…

多线程(如何理解pthread库)

上一节&#xff0c;我们主要介绍了pthread库中一些常见函数的用法&#xff0c;这节我们主要分析一下pthread库到底是什么&#xff1f; 什么是库 我们之前提过&#xff0c;在每一个linux平台下&#xff0c;必定会存在对应的pthread库 它存在于/lib64这个路径底下 换句话说&am…

辅助驾驶功能开发-测试篇(2)-真值系统介绍

1 真值系统概述 1.1 真值评测系统核心应用 快速构建有效感知真值,快速完成感知性能评估,快速分析感知性能缺陷。 主要应用场景包括: 1. 感知算法开发验证: 在算法开发周期中,评测结果可以作为测试报告的一部分,体现算法性能的提升。 2. 遴选供应…

我的企业证书是正常的但是下载应用app到手机提示无法安装“app名字”无法安装此app,因为无法验证其完整性解决方案

我的企业证书是正常的但是下载应用app到手机提示无法安装“app名字”无法安装此app&#xff0c;因为无法验证其完整性解决方案 首先&#xff0c;确保您从可信任的来源下载并安装企业开发者签名过的应用程序。如果您不确定应用程序的来源&#xff0c;建议您联系应用程序提供者…

linux下查找文件的相关命令

linux下查找文件的相关命令 运行环境&#xff1a;centos7 参考来源&#xff1a;man、鸟哥入门书籍 一、脚本文件查找&#xff1a;which/type 1. which man手册描述&#xff1a; 返回当前环境可以被执行的文件&#xff08;或链接&#xff09;的路径。搜索PATH变量匹配参数中…

【PostgreSQL】【存储管理】表和元组的组织方式

外存管理负责处理数据库与外存介质(PostgreSQL8.4.1版本中只支持磁盘的管理操作)的交互过程。在PostgreSQL中&#xff0c;外存管理由SMGR(主要代码在smgr.c中)提供了对外存的统一接口。SMGR负责统管各种介质管理器&#xff0c;会根据上层的请求选择一个具体的介质管理器进行操作…

十四天学会C++之第二天(函数和库)

1. 函数的定义和调用 在C中&#xff0c;函数是组织和结构化代码的关键工具之一。它们允许您将一段代码封装成一个可重复使用的模块&#xff0c;这有助于提高代码的可读性和维护性。 为什么使用函数&#xff1f; 函数在编程中的作用不可小觑。它们有以下几个重要用途&#xf…

WEB3 solidity 带着大家编写测试代码 操作订单 创建/取消/填充操作

好 在我们的不懈努力之下 交易所中的三种订单函数已经写出来了 但是 我们只是编译 确认了 代码没什么问题 但还没有实际的测试过 这个测试做起来 其实就比较的麻烦了 首先要有两个账号 且他们都要在交易所中有存入 我们还是先将 ganache 的虚拟环境启动起来 然后 我们在项目…

EasyX图形库note4,动画及键盘交互

大家好&#xff0c;这里是Dark Flame Master&#xff0c;专栏从这篇开始就会变得很有意思&#xff0c;我们可以利用今天所学的只是实现很多功能&#xff0c;同样为之后的更加好玩的内容打下基础&#xff0c;从这届开始将会利用所学的知识制作一些小游戏&#xff0c;废话不多说&…

第一百六十二回 PopupMenuButton组件

文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了Sliver综合示例相关的内容&#xff0c;本章回中将介绍 PopupMenuButton组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 我们在本章回中介绍的PopupMenuButton组件位于AppBar右侧&#xff0c;通常显…

MacOS怎么安装Nacos(附带:Windows系统)

MacOS安装Nacos&#xff08;一定要配置JDK的环境变量&#xff0c;后面告诉你为什么&#xff1f;&#xff09; &#xff08;1&#xff09;进入Nacos官网&#xff0c;前往githubhomehomehttp://nacos.io/zh-cn/ &#xff08;2&#xff09;点击右下角的releases 然后点击Tags 选择…