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

LeetCode 热题100——链表专题

一、俩数相加

2.俩数相加(题目链接)

思路:这题题目首先要看懂,以示例1为例  即  342+465=807,而产生的新链表为7->0->8.

可以看成简单的从左向右,低位到高位的加法运算,4+6=10,逢10进1,新链表第三位为3+4+1(第二位进的1),需要注意的的点是当9->9->9和9->9->9->9相加,相当于9->9->9->0和9->9->9->9相加

代码实现:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef  struct ListNode  ListNode;ListNode * ListBuyNode(int x){ListNode * node=(ListNode*)malloc(sizeof(ListNode));if(node==NULL){perror("malloc fail:");return NULL;}node->val=x;node->next=NULL;return  node;}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {int ret=0;ListNode *head=(ListNode*)malloc(sizeof(ListNode));//带头单链表ListNode*pcur=head;while(l1||l2||ret){if(l1){ret=ret+l1->val;}if(l2){ret=ret+l2->val;}ListNode *node=ListBuyNode(ret%10);pcur->next=node;pcur=pcur->next;if(l1){l1=l1->next;}if(l2){l2=l2->next;}ret=ret/10;}return head->next;
}

解析:这里使用的是带头单链表,不用考虑头节点初始化问题;还有一点是:当l1和l2都走完时,还要确定进位是否为0,不为0,新链表还得在加一个节点,储存进位。

测试及结果: 

二、回文链表

234.回文链表(题目链接)

思路:1)将链表内容复制到数组里面;

           2)使用双指针法判断是否为回文。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct   ListNode   ListNode;
bool isPalindrome(struct ListNode* head) {assert(head);int arr[100000]={0};int k=0;ListNode*pcur=head;while(pcur){arr[k]=pcur->val;k++;pcur=pcur->next;}for(int i=0,j=k-1;i<j;i++,j--){if(arr[i]!=arr[j]){return false;}}return true;
}

三、相交链表

160.相交链表(题目链接)

思路:这道题的思路比较巧妙,相交链表最关键是节点重合,所以判断条件是节点相等,不是节点的val相等 。

若链表其中一个为NULL,则必定不相交,返回NULL.

分类讨论:

1)链表不相交(假设pheadA的长度为m,headB的长度为n)

1>若m==n,俩链表同时遍历完,相等为NULL

2>若m!=n,headA往后遍历,若遍历结束,则返回到headB的头节点,headB往后遍历,若遍历结束,则返回到headA的头节点,当遍历m+n次,他们都相等为NULL

2)链表相交(假设pheadA的长度为m,headB的长度为n,相交点到headA的头节点距离为a,相交点到headB的头节点距离为b,相交点到末尾的长度为c)

注:a+c=m,b+c=n

1>若m==n,在遍历完第一遍之前,必定有headA==headB!=NULL

2>若m!=n,headA往后遍历,若遍历结束,则返回到headB的头节点,headB往后遍历,若遍历结束,则返回到headA的头节点,当headA遍历a+c+b次,headB遍历b+c+a,同时到达相交点,headA==headB!=NULL

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct  ListNode  ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode *p1=headA;ListNode*p2=headB;if(p1==NULL){return NULL;}if(p2==NULL){return NULL;}while(p1!=p2){p1 = p1 == NULL ? headB : p1->next;p2 = p2 == NULL ? headA : p2->next;}//p1与p2不相交,则为NULL;p1与p2相交,则为不为NULLif(p1==NULL){return NULL;}return p1;
}

四、删除链表倒数第N个节点

19.删除链表的倒数第N个节点

解法一:快慢指针(这里使用无头链表,需要对删除头节点额外考虑) 

typedef struct ListNode ListNode;
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {assert(head);ListNode* fast,*slow;fast=slow=head;if(head->next==NULL)//只有一个节点{free(head);head=NULL;return NULL;}//至少2个节点while(n--){fast=fast->next;}if(fast==NULL)//删除头节点{head=head->next;return head;}while(fast->next){fast=fast->next;slow=slow->next;}ListNode *del=slow->next;slow->next=del->next;free(del);del=NULL;return head;
}

优化快慢指针,引进头节点(哑节点)

 typedef struct ListNode ListNode;
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {assert(head);ListNode* fast,*slow;ListNode*node=(ListNode*)malloc(sizeof(ListNode));node->next=head;fast=slow=node;int m=n+1;while(m--){fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}ListNode*del=slow->next;slow->next=del->next;free(del);del=NULL;return node->next;
}

解法二:遍历链表,找到链表节点数L,用删除指定位置节点方式删除第(L-n+1)个节点即可

相关文章:

LeetCode 热题100——链表专题

一、俩数相加 2.俩数相加&#xff08;题目链接&#xff09; 思路&#xff1a;这题题目首先要看懂&#xff0c;以示例1为例 即 342465807&#xff0c;而产生的新链表为7->0->8. 可以看成简单的从左向右&#xff0c;低位到高位的加法运算&#xff0c;4610&#xff0c;逢…...

植物花粉深度学习图片数据集大合集

最近收集了一波有关于植物花粉的图片数据集&#xff0c;可以用于相关深度学习模型的搭建&#xff0c;废话不多说&#xff0c;上数据集&#xff01;&#xff01;&#xff01; 1、23种花粉类型805张花粉图像数据集 关于此数据&#xff1a;花粉种类和类型的分类是法医抱粉学、考…...

面试算法48:序列化和反序列化二叉树

题目 请设计一个算法将二叉树序列化成一个字符串&#xff0c;并能将该字符串反序列化出原来二叉树的算法。 分析 先考虑如何将二叉树序列化为一个字符串。需要逐个遍历二叉树的每个节点&#xff0c;每遍历到一个节点就将节点的值序列化到字符串中。以前序遍历的顺序遍历二叉…...

【Python基础】Python编程入门自学笔记,基础大全,一篇到底!

&#x1f4e2;&#xff1a;如果你也对机器人、人工智能感兴趣&#xff0c;看来我们志同道合✨ &#x1f4e2;&#xff1a;不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 &#x1f4e2;&#xff1a;文章若有幸对你有帮助&#xff0c;可点赞 &#x1f44d;…...

windows自动登陆

新建文本粘贴下面代码&#xff0c;另存为注册表文件 Windows Registry Editor Version 5.00[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Driver Signing] "Policy"hex:00[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Winlogon]"DefaultUserN…...

5G及其后的5G非地面网络:趋势和研究挑战-HARQ部分

NTN组件纳入5G架构第一步 在NTN SI中定义了一组架构选项。就NT部分而言&#xff0c;已确定了两大类&#xff1a;星载&#xff08;即基于卫星的通信平台&#xff09;和机载&#xff08;即HAPS&#xff09;设备 并行管理HARQ最大进程数 NHARQRTT(NTX−1)2μ NTX&#xff1a;传输…...

【WPF系列】- XAML语法规范

【WPF系列】- XAML语法规范 文章目录 【WPF系列】- XAML语法规范一、概述二、对象元素语法三、特性语法&#xff08;属性&#xff09;四、特性值的处理五、枚举特性值六、属性和事件成员名称引用七、属性元素语法八、集合语法九、XAML 内容属性XAML 内容属性值必须是连续的 十、…...

antv/g6之图布局及切换布局

一般图布局 目前为止&#xff0c;g6的一般图布局已经有13种了&#xff0c;如下: Random Layout&#xff1a;随机布局&#xff1b;Force2 Layout&#xff1a;G6 4.7.0 后支持力导向布局&#xff0c;与 gForce 相比性能更强&#xff1b;GForce Layout&#xff1a;G6 4.0 支持的…...

Wordpress plugin removes ‘/category‘

plugin removes /category from your category permalinks Remove Category URL – WordPress plugin | WordPress.org...

【大数据基础平台】星环TDH社区集群版本部署

&#x1f984; 个人主页——&#x1f390;开着拖拉机回家_大数据运维-CSDN博客 &#x1f390;✨&#x1f341; &#x1fa81;&#x1f341;&#x1fa81;&#x1f341;&#x1fa81;&#x1f341;&#x1fa81;&#x1f341; &#x1fa81;&#x1f341;&#x1fa81;&#x1f…...

【Java】汉诺塔

汉诺塔 汉诺塔&#xff08;Tower of Hanoi&#xff09;&#xff08;河内塔&#xff09;&#xff1a;把圆盘从下面开始按大小顺序重新摆放到另一根柱子上&#xff0c;并且小圆盘上不能放大圆盘&#xff0c;在三根柱子之间一次只能移动一个圆盘。 汉诺塔规则 disk表示圆盘数一次只…...

Java实现对Html文本的处理

1.引入jsoup <dependency><groupId>org.jsoup</groupId><artifactId>jsoup</artifactId><version>1.8.3</version> </dependency> 2. html示例 示例代码&#xff1a; <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1…...

Vue项目创建与启动(2023超详细的图文教程)

目录 一、下载node.js 二、下载vue-cli与webpack插件 三、项目初始化(项目配置详细信息) 四、项目启动 五、Vue项目工程结构&#xff08;扩展知识&#xff09; 一、下载node.js 1.检测是否已经安装过node.js 打开控制台,输入 npm -v如果有会显示对应版本 如果没有会显示…...

EtherCAT主站读取从站EEPROM抓包分析

0 工具准备 1.EtherCAT主站 2.EtherCAT从站&#xff08;本文使用步进电机驱动器&#xff09; 3.Wireshark1 抓包分析 1.1 报文总览 本文让主站去读取从站1字地址为0的EEPROM数据内容&#xff0c;主站读取从站EEPROM数据内容使用Wireshark抓包如下&#xff1a; 1.2 EEPROM读…...

Elasticsearch 8.X 如何生成 TB 级的测试数据 ?

1、实战问题 我只想插入大量的测试数据&#xff0c;不是想测试性能&#xff0c;有没有自动办法生成TB级别的测试数据&#xff1f;有工具&#xff1f;还是说有测试数据集之类的东西&#xff1f;——问题来源于 Elasticsearch 中文社区https://elasticsearch.cn/question/13129 2…...

汽车标定技术(四)--问题分析:多周期测量时上位机显示异常

目录 1.问题现象 2.数据流分析 ​​​​3.代码分析 3.1 AllocDAQ 3.2 AllocOdt 3.3 AllocOdtEntry 4.根因分析及解决方法 4.1 根因分析 4.2 解决方案 1.问题现象 在手撸XCP代码时&#xff0c; DAQ的实现是一大头痛的事情。最初单周期实现还好一点&#xff0c;特别是…...

Flink SQL时间属性和窗口介绍

&#xff08;1&#xff09;概述 时间属性&#xff08;time attributes&#xff09;&#xff0c;其实就是每个表模式结构&#xff08;schema&#xff09;的一部分。它可以在创建表的 DDL 里直接定义为一个字段&#xff0c;也可以在 DataStream 转换成表时定义。 一旦定义了时间…...

Tomcat免安装版修改标题名称和进程

tomcat免安装版启动后闪退问题 问题描述 在官网下载的tomcat免安装版的你安装完环境后发现启动闪退&#xff0c;tomcat启动依赖环境是JDK&#xff0c;所以需要tomcat对应版本的JDK支持。 tomcat8官网下载地址&#xff1a;https://tomcat.apache.org/ JDK环境官网下载地址&…...

vim搜索、替换tab

bibtex 中的缩进可能不一致&#xff0c;强迫症犯了想将&#xff1a; 缩进空格改 tab&#xff1b;行首的多个 tab 改为单个 参考 [1]&#xff0c;空格换 tab 可以&#xff1a; :set noexpandtab :%retab!行首的多个 tab 换单个&#xff1a; :%s/^\t\/\t/gReferences Replac…...

一文读懂ARM安全性架构和可信系统构建要素

一文读懂ARM安全性架构和可信系统构建要素 所谓可信系统&#xff08;trusted system&#xff09;&#xff0c;即能够用于保护密码和加密密钥等资产&#xff08;assets&#xff09;免受一系列的可信攻击&#xff0c;防止其被复制、损坏或不可用&#xff08;unavailable&#xf…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

【版本控制】GitHub Desktop 入门教程与开源协作全流程解析

目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork&#xff08;创建个人副本&#xff09;步骤 2: Clone&#xff08;克隆…...