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.俩数相加(题目链接) 思路:这题题目首先要看懂,以示例1为例 即 342465807,而产生的新链表为7->0->8. 可以看成简单的从左向右,低位到高位的加法运算,4610,逢…...
植物花粉深度学习图片数据集大合集
最近收集了一波有关于植物花粉的图片数据集,可以用于相关深度学习模型的搭建,废话不多说,上数据集!!! 1、23种花粉类型805张花粉图像数据集 关于此数据:花粉种类和类型的分类是法医抱粉学、考…...
面试算法48:序列化和反序列化二叉树
题目 请设计一个算法将二叉树序列化成一个字符串,并能将该字符串反序列化出原来二叉树的算法。 分析 先考虑如何将二叉树序列化为一个字符串。需要逐个遍历二叉树的每个节点,每遍历到一个节点就将节点的值序列化到字符串中。以前序遍历的顺序遍历二叉…...
【Python基础】Python编程入门自学笔记,基础大全,一篇到底!
📢:如果你也对机器人、人工智能感兴趣,看来我们志同道合✨ 📢:不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍…...
windows自动登陆
新建文本粘贴下面代码,另存为注册表文件 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部分而言,已确定了两大类:星载(即基于卫星的通信平台)和机载(即HAPS)设备 并行管理HARQ最大进程数 NHARQRTT(NTX−1)2μ NTX:传输…...
【WPF系列】- XAML语法规范
【WPF系列】- XAML语法规范 文章目录 【WPF系列】- XAML语法规范一、概述二、对象元素语法三、特性语法(属性)四、特性值的处理五、枚举特性值六、属性和事件成员名称引用七、属性元素语法八、集合语法九、XAML 内容属性XAML 内容属性值必须是连续的 十、…...
antv/g6之图布局及切换布局
一般图布局 目前为止,g6的一般图布局已经有13种了,如下: Random Layout:随机布局;Force2 Layout:G6 4.7.0 后支持力导向布局,与 gForce 相比性能更强;GForce Layout:G6 4.0 支持的…...
Wordpress plugin removes ‘/category‘
plugin removes /category from your category permalinks Remove Category URL – WordPress plugin | WordPress.org...
【大数据基础平台】星环TDH社区集群版本部署
🦄 个人主页——🎐开着拖拉机回家_大数据运维-CSDN博客 🎐✨🍁 🪁🍁🪁🍁🪁🍁🪁🍁 🪁🍁🪁…...
【Java】汉诺塔
汉诺塔 汉诺塔(Tower of Hanoi)(河内塔):把圆盘从下面开始按大小顺序重新摆放到另一根柱子上,并且小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 汉诺塔规则 disk表示圆盘数一次只…...
Java实现对Html文本的处理
1.引入jsoup <dependency><groupId>org.jsoup</groupId><artifactId>jsoup</artifactId><version>1.8.3</version> </dependency> 2. html示例 示例代码: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1…...
Vue项目创建与启动(2023超详细的图文教程)
目录 一、下载node.js 二、下载vue-cli与webpack插件 三、项目初始化(项目配置详细信息) 四、项目启动 五、Vue项目工程结构(扩展知识) 一、下载node.js 1.检测是否已经安装过node.js 打开控制台,输入 npm -v如果有会显示对应版本 如果没有会显示…...
EtherCAT主站读取从站EEPROM抓包分析
0 工具准备 1.EtherCAT主站 2.EtherCAT从站(本文使用步进电机驱动器) 3.Wireshark1 抓包分析 1.1 报文总览 本文让主站去读取从站1字地址为0的EEPROM数据内容,主站读取从站EEPROM数据内容使用Wireshark抓包如下: 1.2 EEPROM读…...
Elasticsearch 8.X 如何生成 TB 级的测试数据 ?
1、实战问题 我只想插入大量的测试数据,不是想测试性能,有没有自动办法生成TB级别的测试数据?有工具?还是说有测试数据集之类的东西?——问题来源于 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代码时, DAQ的实现是一大头痛的事情。最初单周期实现还好一点,特别是…...
Flink SQL时间属性和窗口介绍
(1)概述 时间属性(time attributes),其实就是每个表模式结构(schema)的一部分。它可以在创建表的 DDL 里直接定义为一个字段,也可以在 DataStream 转换成表时定义。 一旦定义了时间…...
Tomcat免安装版修改标题名称和进程
tomcat免安装版启动后闪退问题 问题描述 在官网下载的tomcat免安装版的你安装完环境后发现启动闪退,tomcat启动依赖环境是JDK,所以需要tomcat对应版本的JDK支持。 tomcat8官网下载地址:https://tomcat.apache.org/ JDK环境官网下载地址&…...
vim搜索、替换tab
bibtex 中的缩进可能不一致,强迫症犯了想将: 缩进空格改 tab;行首的多个 tab 改为单个 参考 [1],空格换 tab 可以: :set noexpandtab :%retab!行首的多个 tab 换单个: :%s/^\t\/\t/gReferences Replac…...
一文读懂ARM安全性架构和可信系统构建要素
一文读懂ARM安全性架构和可信系统构建要素 所谓可信系统(trusted system),即能够用于保护密码和加密密钥等资产(assets)免受一系列的可信攻击,防止其被复制、损坏或不可用(unavailable…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
