当前位置: 首页 > news >正文

力扣练习——链表在线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;
}

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

相关文章:

力扣练习——链表在线OJ

目录 提示&#xff1a; 一、移除链表元素 题目&#xff1a; 解答&#xff1a; 二、反转链表 题目&#xff1a; 解答&#xff1a; 三、找到链表的中间结点 题目&#xff1a; 解答&#xff1a; 四、合并两个有序链表&#xff08;经典&#xff09; 题目&#xff1a; 解…...

四、互联网技术——局域网拓扑结构

文章目录 一、局域网拓扑结构二、虚拟局域网VLAN三、交换机VLAN划分四、VLAN的作用五、交换机的端口类型六、经典三层网络架构七、例题:局域网带宽利用分析八、网络安全基础九、恶意软件十、防火墙与入侵检测技术 一、局域网拓扑结构 局域网的主要特征由网络的拓扑结构、所采用…...

Spring Webflux DispatcherHandler源码整理

DispatcherHandler的构造(以RequestMappingHandlerMapping为例) WebFluxAutoConfiguration中EnableWebFluxConfiguration继承WebFluxConfigurationSupportBean public DispatcherHandler webHandler() {return new DispatcherHandler(); }DispatcherHandler#setApplicationCon…...

【Netty】ByteToMessageDecoder源码解析

目录 1.协议说明 2.类的实现 3.Decoder工作流程 4.源码解析 4.1 ByteToMessageDecoder#channelRead 4.2 累加器Cumulator 4.3 解码过程 4.4 Decoder实现举例 5. 如何开发自己的Decoder 1.协议说明 Netty框架是基于Java NIO框架&#xff0c;性能彪悍&#xff0c;支持的协…...

DevEco Studio设置Nodejs提示路径只能包含英文、数字、下划线等

安装DevEco Studio 3.1.1 Release 设置Nodejs路径使用nodejs默认安装路径 &#xff08;C:\Program Files\nodejs&#xff09; 提示只能包含英文、数字、下划线等 , 不想在安装nodejs请往下看 nodejs默认路径报错 修改配置文件 1、退出DevEco Studio 2、打开配置文件 cmd控制台…...

大模型 Decoder 的生成策略

本文将介绍以下内容&#xff1a; IntroductionGreedy Searchbeam searchSamplingTop-K SamplingTop-p (nucleus) sampling总结 一、Introduction 1、简介 近年来&#xff0c;由于在数百万个网页数据上训练的大型基于 Transformer 的语言模型的兴起&#xff0c;开放式语言生…...

队列和栈相互实现

相关题目 225. 用队列实现栈&#xff1a;弹出元素时&#xff0c;将对首的元素出列加到队尾&#xff0c;直到只剩下初始队列时队尾一个元素为止&#xff0c;然后弹出这个元素&#xff0c;即可实现LIFO 232. 用栈实现队列&#xff1a;用两个栈实现队列的功能&#xff0c;出栈时&a…...

Node.js 是如何处理请求的

前言&#xff1a;在服务器软件中&#xff0c;如何处理请求是非常核心的问题。不管是底层架构的设计、IO 模型的选择&#xff0c;还是上层的处理都会影响一个服务器的性能&#xff0c;本文介绍 Node.js 在这方面的内容。 TCP 协议的核心概念 要了解服务器的工作原理首先需要了…...

数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素。…...

SpringBoot快速入门

搭建SpringBoot工程&#xff0c;定义hello方法&#xff0c;返回“Hello SpringBoot” ②导入springboot工程需要继承的父工程&#xff1b;以及web开发的起步依赖。 ③编写Controller ④引导类就是SpringBoot项目的一个入口。 写注解写main方法调用run方法 快速构建SpringBoo…...

深度学习笔记_4、CNN卷积神经网络+全连接神经网络解决MNIST数据

1、首先&#xff0c;导入所需的库和模块&#xff0c;包括NumPy、PyTorch、MNIST数据集、数据处理工具、模型层、优化器、损失函数、混淆矩阵、绘图工具以及数据处理工具。 import numpy as np import torch from torchvision.datasets import mnist import torchvision.transf…...

高效的开发流程搭建

目录 1. 搭建 AI codebase 环境kaggle的服务器1. 搭建 AI codebase 环境 python 、torch 以及 cuda版本,对AI的影响最大。不同的版本,可能最终计算出的结果会有区别。 硬盘:PCIE转SSD的卡槽,, GPU: 软件源: Anaconda: 一定要放到固态硬盘上。 VS code 的 debug功能…...

浅谈OV SSL 证书的优势

随着网络威胁日益增多&#xff0c;保护网站和用户安全已成为每个企业和组织的重要任务。在众多SSL证书类型中&#xff0c;OV&#xff08;Organization Validation&#xff09;证书以其独特的优势备受关注。让我们深入探究OV证书的优势所在&#xff0c;为网站安全搭建坚实的防线…...

一篇博客学会系列(3) —— 对动态内存管理的深度讲解以及经典笔试题的深度解析

目录 动态内存管理 1、为什么存在动态内存管理 2、动态内存函数的介绍 2.1、malloc和free 2.2、calloc 2.3、realloc 3、常见的动态内存错误 3.1、对NULL指针的解引用操作 3.2、对动态开辟空间的越界访问 3.3、对非动态开辟内存使用free释放 3.4、使用free释放一块动态…...

【C++ techniques】虚化构造函数、虚化非成员函数

constructor的虚化 virtual function&#xff1a;完成“因类型而异”的行为&#xff1b;constructor&#xff1a;明确类型时构造函数&#xff1b;virtual constructor&#xff1a;视其获得的输入&#xff0c;可产生不同的类型对象。 //假如写一个软件&#xff0c;用来处理时事…...

蓝牙核心规范(V5.4)11.6-LE Audio 笔记之初识音频位置和通道分配

专栏汇总网址:蓝牙篇之蓝牙核心规范学习笔记(V5.4)汇总_蓝牙核心规范中文版_心跳包的博客-CSDN博客 爬虫网站无德,任何非CSDN看到的这篇文章都是盗版网站,你也看不全。认准原始网址。!!! 音频位置 在以前的每个蓝牙音频规范中,只有一个蓝牙LE音频源和一个蓝牙LE音频接…...

mysql双主+双从集群连接模式

架构图&#xff1a; 详细内容参考&#xff1a; 结果展示&#xff1a; 178.119.30.14(主) 178.119.30.15(主) 178.119.30.16(从) 178.119.30.17(从)...

嵌入式中如何用C语言操作sqlite3(07)

sqlite3编程接口非常多&#xff0c;对于初学者来说&#xff0c;我们暂时只需要掌握常用的几个函数&#xff0c;其他函数自然就知道如何使用了。 数据库 本篇假设数据库为my.db,有数据表student。 nonamescore4嵌入式开发爱好者89.0 创建表格语句如下&#xff1a; CREATE T…...

RandomForestClassifier 与 GradientBoostingClassifier 的区别

RandomForestClassifier&#xff08;随机森林分类器&#xff09;和GradientBoostingClassifier&#xff08;梯度提升分类器&#xff09;是两种常用的集成学习方法&#xff0c;它们之间的区别分以下几点。 1、基础算法 RandomForestClassifier&#xff1a;随机森林分类器是基于…...

计组——I/O方式

一、程序查询方式 CPU不断轮询检查I/O控制器中“状态寄存器”&#xff0c;检测到状态为“已完成”之后&#xff0c;再从数据寄存器取出输入数据。 过程&#xff1a; 1.CPU执行初始化程序&#xff0c;并预置传送参数&#xff1b;设置计数器、设置数据首地址。 2. 向I/O接口发…...

jsbridge实战2:Swift和h5的jsbridge通信

[[toc]] demo1: 文本通信 h5 -> app 思路&#xff1a; h5 全局属性上挂一个变量app 接收这个变量的内容关键API: navigation代理 navigationAction.request.url?.absoluteString // 这个变量挂载在 request 的 url 上 &#xff0c;在浏览器实际无法运行&#xff0c;因…...

集合原理简记

HashMap 无论在构造函数是否指定数组长度&#xff0c;进行的都是延迟初始化 构造函数作用&#xff1a; 阈值&#xff1a;threshold&#xff0c;每次<<1 &#xff0c;数组长度 负载因子 无参构造&#xff1a;设置默认的负载因子 有参&#xff1a;可以指定初始容量或…...

机器学习的超参数 、训练集、归纳偏好

一、介绍 超参数&#xff08;Hyperparameters&#xff09;和验证集&#xff08;Validation Set&#xff09;是机器学习中重要的概念&#xff0c;用于调整模型和评估其性能。 超参数&#xff1a; 超参数是在机器学习模型训练过程中需要手动设置的参数&#xff0c;而不是从数据…...

Leetcode1071. 字符串的最大公因子(三种方法,带详细解析)

Leetcode1071. 字符串的最大公因子 对于字符串 s 和 t&#xff0c;只有在 s t … t&#xff08;t 自身连接 1 次或多次&#xff09;时&#xff0c;我们才认定 “t 能除尽 s”。 给定两个字符串 str1 和 str2 。返回 最长字符串 x&#xff0c;要求满足 x 能除尽 str1 且 x 能…...

如何像人类一样写HTML之图像标签,超链接标签与多媒体标签

文章目录 前言一、图像标签1.1 什么是图像标签&#xff1f;2.2 如何使用图像标签&#xff1f; 二、超链接标签2.1 什么是超链接标签&#xff1f;2.2 如何使用超链接标签&#xff1f; 三、多媒体标签3.1 什么是多媒体标签&#xff1f;3.2 如何使用多媒体audio标签&#xff1f;3.…...

1300*C. Rumor(并查集贪心)

解析&#xff1a; 并查集&#xff0c;求每个集合的最小费用。 每次合并集合的时候&#xff0c;根节点保存当前集合最小的费用。 #include<bits/stdc.h> using namespace std; #define int long long const int N1e55; int n,m,a[N],p[N],cnt[N]; int find(int x){retur…...

python实用小代码(数据分析向)

一、python实现31省市名称替换 首先定义了一个字典province_dict&#xff0c;其中包含每个省市的无缩写名称与其标准名称之间的映射。然后&#xff0c;我们使用map()函数将每个省市名称从无缩写名称转换为标准名称&#xff0c;并将结果存储在新列省市标准名称中。 province_di…...

【oncmdmsg 鼠标】2023/8/19 上午9:50:14

2023/8/19 上午9:50:14 oncmdmsg 鼠标 2023/8/19 上午9:50:22 抱歉,您提到的 “oncmdmsg” 和 “鼠标” 是什么?请提供更多上下文信息,我将尽力帮助您。 2023/8/19 上午9:51:43 OnCmdMsg 2023/8/19 上午9:52:21 “OnCmdMsg” 是一个在 MFC (Microsoft Foundation Cla…...

插入排序:简单而有效的排序方法

在计算机科学中&#xff0c;排序算法是一个重要且常见的主题&#xff0c;它们用于对数据进行有序排列。插入排序&#xff08;Insertion Sort&#xff09;是其中一个简单但有效的排序算法。本文将详细解释插入排序的原理和步骤&#xff0c;并提供Java语言的实现示例。 插入排序的…...

OpenGL之光照贴图

我们需要拓展之前的系统,引入漫反射和镜面光贴图(Map)。这允许我们对物体的漫反射分量和镜面光分量有着更精确的控制。 漫反射贴图 我们希望通过某种方式对物体的每个片段单独设置漫反射颜色。我们仅仅是对同样的原理使用了不同的名字:其实都是使用一张覆盖物体的图像,让我…...