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

LeetCode 热题100——链表专题(二)

一、环形链表

141.环形链表(题目链接)

思路:使用快慢指针,慢指针走一步,快指针走俩步,如果是环形链表,那么快慢指针一定相遇,如果不是环形结构那么快指针或者快指针的next一定先为NULL.

代码如下:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef   struct ListNode ListNode ;
bool hasCycle(struct ListNode *head) {if(head==NULL||head->next==NULL){return false;}ListNode* fast=head;ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;}

 二、环形链表||

142.环形链表||(题目链接)

思路:用快慢指针方式。慢指针走一步,快指针走俩步,如果是环形,那么快慢指针第一次相遇快指针走的次数是慢指针的俩倍,S(快)=2k,S(慢)=k,而且快指针比慢指针多走一个环形(这里可以验证:快指针第一次超越慢指针不可能越过慢指针,必定重合,可自行画图解析) ,即k=一圈的节点数,也就是慢指针此时从第一节点出发走了一个环形节点数步数,若此时让快指针从头节点出发,慢指针从原位置出发,俩指针每次都走一步,快指针走a步到达入环的第一个节点,那么慢指针是不是走a+k次呢?是不是可以认为慢指针先走a次,到达入环第一个节点,然后再走(k次=一圈)回到原位置呢。

代码如下: 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {if(head==NULL||head->next==NULL){return NULL;}ListNode* fast=head;ListNode*slow=head;do{slow=slow->next;fast=fast->next->next;}while((fast!=NULL&&fast->next!=NULL&&slow!=fast));if(fast==NULL||fast->next==NULL){return NULL;}if(slow==fast){fast=head;}while(fast!=slow){slow=slow->next;fast=fast->next;}return fast;
}

三、俩俩交换链表中的节点

 24.俩俩交换链表中的节点

解法一:递归思想

1)将大化小:将整个链表俩俩交换节点化为前俩个节点交换后指向后面整体俩俩交换的部分链表,以此层层递进,将整体化为部分

2)出口:最后剩一个节点或NULL,则返回此节点

创造新的头节点为链表的头节点的第二个节点,让原来的头节点指向后面交换返回的节点,让新头节点指向原头节点,返回新头节点 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* swapPairs(struct ListNode* head) {if(head==NULL||head->next==NULL){return head;}ListNode*  newhead=head->next;head->next=swapPairs(newhead->next);newhead->next=head;return newhead;
}

 解法二:迭代思想

创造一个哑节点,为node,紧跟后面的节点为node1和node2,每次交换node1和node2的位置,然后node走到交换后node1的位置,继续交换后面俩个节点的位置,直到后面没有节点或只有一个节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* swapPairs(struct ListNode* head) {if(head==NULL||head->next==NULL){return head;}ListNode*node=(ListNode*)malloc(sizeof(ListNode));ListNode*tmp=node;tmp->next=head;while(tmp->next!=NULL&&tmp->next->next!=NULL){ListNode*node1=tmp->next;ListNode*node2=tmp->next->next;node1->next=node2->next;node2->next=node1;tmp->next=node2;tmp=node1;}return node->next;
}

四、排序链表

148.排序链表(题目链接) 

 

 思路: 用一个数组存储链表的所有数据, 然后对数组进行快排, 然后将数据填入链表 ,返回即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/int compare(const void *e1,const void *e2){return *((int*)e1)-*((int*)e2);}typedef struct ListNode ListNode;
struct ListNode* sortList(struct ListNode* head) {if(head==NULL||head->next==NULL){return head;}//至少俩个节点int arr[50000];ListNode*pcur=head;int i=0;while(pcur){arr[i]=pcur->val;i++;pcur=pcur->next;}qsort(arr,i,sizeof(int),compare);pcur=head;for(int j=0;j<i;j++){pcur->val=arr[j];pcur=pcur->next;}return head;
}

相关文章:

LeetCode 热题100——链表专题(二)

一、环形链表 141.环形链表&#xff08;题目链接&#xff09; 思路&#xff1a;使用快慢指针&#xff0c;慢指针走一步&#xff0c;快指针走俩步&#xff0c;如果是环形链表&#xff0c;那么快慢指针一定相遇&#xff0c;如果不是环形结构那么快指针或者快指针的next一定先为N…...

【Rust日报】2023-11-06 ESP上使用 Rust实现 SNTP协议

ESP上使用 Rust实现 SNTP协议 在这篇文章中&#xff0c;作者使用 ESP 和 Rust 使用 SNTP 协议将设备系统时间与网络时间同步。 SNTP 是 Simple Network Time Protocol 的缩写&#xff0c;它是一种用于在计算机系统之间通过分组交换、可变延迟数据网络进行时钟同步的网络协议。S…...

LibreOJ - 2874 历史研究 (回滚莫队)

回滚莫队就是在基础莫队的前提下&#xff0c;用更多的增加操作代替了减操作。 分成两种情况 1、一个询问的整个区间都在一个块儿里&#xff1b;这种情况直接暴力求即可&#xff0c;因为在一个块儿里&#xff0c;时间复杂度不会高。 2、一个询问的整个区间不在一个块儿里&#…...

人工智能-卷积神经网络之多输入多输出通道

多输入多输出通道 每个图像的多个通道和多层卷积层。例如彩色图像具有标准的RGB通道来代表红、绿和蓝。 但是到目前为止&#xff0c;我们仅展示了单个输入和单个输出通道的简化例子。 这使得我们可以将输入、卷积核和输出看作二维张量。 当我们添加通道时&#xff0c;我们的输…...

Open3D(C++) Umeyama算法求两个点云的变换矩阵

目录 一、算法原理1、原理概述2、主要函数3、算法源码4、参考文献二、代码实现1、详细过程2、调用函数三、结果展示四、相关链接一、算法原理 1、原理概述 原版英文论文有很详细的公式推导过程,考虑到论文年代久远,存在下载困难问题。因此,这里给出论文中的推导过程截图。...

【C++】从入门到精通第二弹——类的构造与析构函数

这里写目录标题 类的构造函数类的析构函数 写在最前面的话 ——构造函数和析构函数是两个特殊的成员函数&#xff0c;都没有返回值&#xff0c;构造函数名和类名相同&#xff0c;析构函数名只是在类名前加上 ~ 构造函数主要用来在创建对象时给对象中的数据成员赋值&#xff0c;…...

C#8.0本质论第十一章--异常处理

C#8.0本质论第十一章–异常处理 11.1多异常类型 用关键字throw抛出异常实例&#xff0c;所选的异常类型应该能最好地说明发生异常的背景。 11.2捕捉异常 发生异常时&#xff0c;会跳转到与异常类型最匹配的catch块执行&#xff0c;匹配度由继承链决定。 从C#6.0起&#xf…...

FPGA高端项目:图像缩放+GTP+UDP架构,高速接口以太网视频传输,提供2套工程源码加QT上位机源码和技术支持

目录 1、前言免责声明本项目特点 2、相关方案推荐我这里已有的 GT 高速接口解决方案我这里已有的以太网方案我这里已有的图像处理方案 3、设计思路框架设计框图视频源选择ADV7611 解码芯片配置及采集动态彩条跨时钟FIFO图像缩放模块详解设计框图代码框图2种插值算法的整合与选择…...

ansible安装和常见模块

文章目录 ansible的安装1.1 yum install epel-release.noarch1.2配置epel源的baseurl1.3安装ansible1.4安装ansible报错问题1.5 yum卸载 ansible的安装 ansible是由epel源提供的&#xff0c;所以需要配置epel源。要么通过配置好的baseos源直接执行“yum install epel-release.…...

【Python基础】 Python设计模式之单例模式介绍

单例模式 1.设计模式2.单例设计模式的应用场景3.new方法4. Python 中的单例 1.设计模式 设计模式 是 前人工作的总结和提炼&#xff0c;通常&#xff0c;被人们广泛流传的设计模式都是针对 某一特定问题 的成熟的解决方案使用 设计模式 是为了可重用代码、让代码更容易被他人理…...

算法小白的心得笔记:关于Nan

NaN 是什么 在C中&#xff0c;NaN&#xff08;Not a Number&#xff09;是一种特殊的浮点数值&#xff0c;用于表示无法表示的数值或未定义的操作&#xff0c;例如0除以0。如果你的double类型变量显示为NaN&#xff0c;那么可能是在计算过程中出现了这种未定义的操作。 如果你…...

Photoshop 2023 v24.7

Photoshop是一款强大的图像编辑软件&#xff0c;被广泛应用于图像处理、图形设计、数字绘画等领域。它提供了丰富的图像编辑功能&#xff0c;可以用于调整图像的色彩、亮度、对比度等&#xff0c;添加特效、滤镜&#xff0c;以及进行复杂的图像合成和修复。 以下是Adobe Photo…...

进程间通信(IPC)-管道、消息队列、信号量、共享存储、socket

进程间通信&#xff08;IPC&#xff0c;InterProcess Communication&#xff09;是指在不同进程之间传播或交换信息。 IPC的方式通常有管道&#xff08;包括无名管道PIPE和命名管道FIFO&#xff09;、消息队列、信号量、共享存储、Socket、Streams等。其中 Socket和Streams支持…...

「Verilog学习笔记」使用generate…for语句简化代码

专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点&#xff0c;刷题网站用的是牛客网 分析 generate…for语句是Verilog HDL语言特有的语句&#xff0c;使用循环结构编写可综合的多个形式相近的代码&#xff0c;循环变量必须由特定关键字genvar声明。 timesca…...

互联网Java工程师面试题·Spring篇·第七弹

目录 36、什么是基于 Java 的 Spring 注解配置? 给一些注解的例子. 37、什么是基于注解的容器配置? 38、怎样开启注解装配&#xff1f; 39、Required 注解 40、Autowired 注解 41、Qualifier 注解 42、在 Spring 框架中如何更有效地使用 JDBC? 43、JdbcTemplate 44…...

mysql驱动包引起的告警问题using SSL the verifyServerCertificate property is set to ‘false‘

tomcat启动时报以下ssl的连接错误&#xff0c;mysql版本为5.7.17&#xff0c;虽然系统可以使用&#xff0c;但是日志量太大&#xff0c;还是处理下&#xff0c;只需要修改mysql的连接格式&#xff1a; url.db “jdbc:mysql://localhost:3306/disis3?userroot&passwordXXXX…...

draw.io与项目管理——如何利用流程图工具提高项目管理效率

draw.io 是一款强大的图形绘制工具&#xff0c;用于创建各种类型的图表、流程图、组织结构图、网络图和平面设计等。它提供了丰富的绘图工具和预定义的图形库&#xff0c;使用户能够轻松创建专业水平的图形作品。 draw.io具有直观的界面和简单易用的功能&#xff0c;适合各种用…...

LoRaWAN物联网架构

与其他网关一样&#xff0c;LoRaWAN网关也需要在规定的工作频率上工作。在特定国家部署网关时&#xff0c;必须要遵循LoRa联盟的区域参数。不过&#xff0c;它是没有通用频率的&#xff0c;每个国家对使用非授权MHZ频段都有不同的法律规定。例如&#xff0c;中国的LoRaWAN频段是…...

数据结构(五):哈希表及面试常考的算法

一、哈希表介绍 1、定义 哈希表&#xff0c;也叫散列表&#xff0c;是根据关键码和值 (key和value) 直接进行访问的数据结构&#xff0c;通过key和value来映射到集合中的一个位置&#xff0c;这样就可以很快找到集合中的对应元素。例如&#xff0c;下列键(key)为人名&#xf…...

水利部加快推进小型水库除险加固,大坝安全监测是重点

国务院常务会议明确到2025年前&#xff0c;完成新出现病险水库的除险加固&#xff0c;配套完善重点小型水库雨水情和安全监测设施&#xff0c;实现水库安全鉴定和除险加固常态化。 为加快推进小型水库除险加固前期工作&#xff0c;水利部协调财政部提前下达了2023年度中央补助…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...