链表学习之找到两个链表相交的第一个节点
链表解题技巧
- 额外的数据结构(哈希表);
- 快慢指针;
- 虚拟头节点;
找到两个链表相交的第一个节点
给定两个链表,这两个链表可能有环,可能无环。判断这两个链表是否相交,相交则返回第一个相交的节点,不相交则返回nullptr。
首先,需要判断两个链表是否有环,有环的话入环节点的位置在哪?
然后,分情况判断两个链表是否相交:
- 两个无环链表:对于两个无环链表;
- 一个有环一个无环:不可能相交;
- 两个有环链表:入环点相同(一定相交)、入环点不相同;
ListNode* LinkedList::findFirstIntersection(ListNode *head1, ListNode *head2) {if (head1 == nullptr || head2 == nullptr) {return nullptr;}// has cycleListNode *loop1 = hasCycle(head1);ListNode *loop2 = hasCycle(head2);// if (loop1 == nullptr && loop2 == nullptr) return findFirstIntersectionWithNoLoop(head1, head2);if (loop1 != nullptr && loop2 != nullptr) return findFirstIntersectionWithLoops(head1, loop1, head2, loop2);return nullptr;
}
链表是否有环
方法1:哈希表(时:O(N),空:O(N))
使用哈希表,在链表遍历过程中,判断该节点是否在哈希表中:
- 该节点在表中,则说明有环,此时为入环第一个节点,返回该节点并退出;
- 该节点不在表中,说明无环,将节点指针加入表中,继续遍历;
- 遍历到空,则说明无环。
ListNode* LinkedList::hasCycleBySet(ListNode *head) {if (head == nullptr || head->next == nullptr) return nullptr;std::unordered_set<ListNode*> set;ListNode *cur = head;while (cur) {if (set.find(cur) != set.end()) {return cur;}set.insert(cur);cur = cur->next;}return nullptr;
}
方法2:快慢指针(时:O(N), 空:O(1))
在快慢指针遍历链表的过程中,如果快指针遍历到nullptr,则说明无环。
如果有环,快慢指针一定会在环内相遇,当相遇发生之后,快指针回到头节点,慢指针不动,快慢指针同时一次一步的移动,直至相遇,相遇的位置即为入环的第一个节点。
ListNode* LinkedList::hasCycle(ListNode *head) {if (head == nullptr || head->next == nullptr) return nullptr;ListNode *slow = head;ListNode *fast = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) {fast = head;while (fast != slow) {slow = slow->next;fast = fast->next;}return slow;}}return nullptr;
}
Notes
fast和slow必须同时从head出发!(fast=head->next,slow=head这样的出发就会差一个节点,永远无法结束)
链表相交
无环链表相交
最好理解和想到的方法就是,遍历两个链表,计算出两个链表的长度差值,让长链表先移动差值步,接着继续同时遍历,直到相遇或都为nullptr。
ListNode* LinkedList::findFirstIntersectionWithNoLoop(ListNode *head1, ListNode *head2) {ListNode *cur1 = head1;ListNode *cur2 = head2;int diff = 0;while (cur1) {cur1 = cur1->next;diff++;}while (cur2) {cur2 = cur2->next;diff--;}cur1 = diff > 0 ? head1 : head2; // cur1 -> the longer listcur2 = cur1 == head2 ? head1 : head2;diff = diff < 0 ? -diff : diff; // abs// cur1 move diff steps firstwhile (diff--) cur1 = cur1->next;while (cur1 != cur2) {cur1 = cur1->next;cur2 = cur2->next;}return cur1;
}
或者使用交换遍历的方式,因为无论如何两个链表都遍历的话,最后要不就相交,要不就都为nullptr。
注意,两个节点和一个节点相交时的循环判断。
ListNode* LinkedList::findFirstIntersectionWithNoLoopEx(ListNode *head1, ListNode *head2) {ListNode *cur1 = head1;ListNode *cur2 = head2;while ( cur1 != cur2 ) {cur1 = cur1 ? cur1->next : head2;cur2 = cur2 ? cur2->next : head1;}return cur1;
}
有环链表相交
有环链表有入环节点相同和入环节点不同两种情况:
- 入环节点相同的话肯定相交,交点也一定在头节点到入环节点之间,等价于无环链表相交;
- 入环节点不同的情况下:如果相交则,这两个节点一定都在一个环上,从其中一个节点开始遍历,到回到这个节点的过程中,如果没有遇到另外一个节点,则说明不相交,反之相交,随意返回其中一个节点即可。
ListNode* LinkedList::findFirstIntersectionWithLoops(ListNode *head1, ListNode *loop1, ListNode *head2, ListNode *loop2) {if (loop1 == loop2) {ListNode *cur1 = head1;ListNode *cur2 = head2;while (cur1 != cur2) {cur1 = cur1->next == loop1->next ? head2 : cur1->next;cur2 = cur2->next == loop1->next ? head1 : cur2->next;}return cur1;} else {ListNode *cur = loop1->next;while (cur != loop1) {cur = cur->next;if (cur == loop2) return cur;}return nullptr;}
}
相关文章:
链表学习之找到两个链表相交的第一个节点
链表解题技巧 额外的数据结构(哈希表);快慢指针;虚拟头节点; 找到两个链表相交的第一个节点 给定两个链表,这两个链表可能有环,可能无环。判断这两个链表是否相交,相交则返回第一…...
【Kubernetes】【十一】Pod详解 Pod的生命周期
Pod生命周期 我们一般将pod对象从创建至终的这段时间范围称为pod的生命周期,它主要包含下面的过程: pod创建过程 运行初始化容器(init container)过程 运行主容器(main container) 容器启动后钩子&#…...
Connext DDS录制服务 Recording Service(1)
1 序言 1.1 简介 RTI记录服务包括以下工具: •记录服务,一种RTI Connext DDS应用程序,用于记录主题和发现数据。记录服务记录数据更新以及时间戳,因此您可以查看或回放系统中随时间发生的数据更新。默认情况下,记录的数据存储在SQLite文件中。录制服务还具有一个API,用于…...
vTESTstudio - VT System CAPL Functions - VT2004(续2)
不要沮丧,不必惊慌,做努力爬的蜗牛或坚持飞的笨鸟,我们试着长大,一路跌跌撞撞,哪怕遍体鳞伤。vtsSetPWMVoltageLow - 设置PWM输出上的低电压功能:指定数字输出信号(尤其是PWM信号)输…...
每天一个linux命令---awk
awk命令 1. 简介 awk是一种处理文本文件的语言,是一个强大的文本分析工具,grep、sed、awk并称为shell中文本处理的三剑客。 AWK 是一种处理文本文件的语言,是一个强大的文本分析工具。 之所以叫 AWK 是因为其取了三位创始人 Alfred Aho&am…...
Open3D 点云旋转之轴角式(Python版本)
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 三维空间中表示旋转的方法有很多种,轴角式是其中非常经典的一种表示方式。虽然欧拉角表示旋转的方法很是常用,但欧拉角存在着万向锁这个问题,因此轴角式旋转在旋转使用中更为合适。其原理也很是明了,如下所述:…...
Error: Timeout trying to fetch resolutions from npm
文章目录问题描述【最终解决】我搜索到的解决方案npmjs 该依赖各版本列表及对应的被下载次数github issue 说降级到0.0.3就可以正常运行了SOF 也说降级别到0.0.3问题描述 在项目里用到了 "preinstall": "npx npm-force-resolutions"配置,在一台…...
Python基础3
目录 1. 函数多返回值 2. 函数多种传参方式 3. 匿名函数 3.1 函数作为参数传递 3.2 lambda匿名函数 4. 文件的读取操作 4.1 open()打开函数 4.2 读操作方法 4.3 文件的写入 4.4 文件的追加 5. 异常的捕获方法 5.1 捕获常规异常 5.2 捕获指定…...
高可用集群(HAC)
1、高可用集群keepalive说明 高可用定义: 目的:尽可能的提高服务的可用性 99%、99.9%、99.99%、99.999% 实现原理:心跳检测服务: 有状态: MySQL 无状态: apacheLVS Keepalive原理 案例环境专为 LVS和…...
python基于django微信小程序的适老化老人健康预警小程序
随着信息技术和网络技术的飞速发展,人类已进入全新信息化时代,传统管理技术已无法高效,便捷地管理信息。为了迎合时代需求,优化管理效率,各种各样的管理系统应运而生,各行各业相继进入信息管理时代, 适老化老人健康预警微信小程序就是信息时代变革中的产物之一。 任何系统都要遵…...
基于微信小程序图书馆管理系统
开发工具:IDEA、微信小程序服务器:Tomcat9.0, jdk1.8项目构建:maven数据库:mysql5.7前端技术:vue、uniapp服务端技术:springbootmybatis-plus本系统分微信小程序和管理后台两部分,项…...
将镭神C32激光雷达的PointXYZ数据转化为PointXYZIR格式 - 附代码
之前遇到过“镭神32线激光雷达ROS下运行fromRosMsg()报错 Failed to find match for field “intensity“ 问题”, 当时确定了是镭神C32雷达缺少相应字段,并记录博客【学习记录】镭神32线激光雷达ROS下运行fromRosMsg()报错 Failed to find match for fi…...
高级前端一面面试题集锦
详细说明 Event loop 众所周知 JS 是门非阻塞单线程语言,因为在最初 JS 就是为了和浏览器交互而诞生的。如果 JS 是门多线程的语言话,我们在多个线程中处理 DOM 就可能会发生问题(一个线程中新加节点,另一个线程中删除节点&#…...
Java基础 -- List集合
Java基础 -- List集合1. Introduction1.1 好处1.2 常用泛型2. 交集,差集等2.1 自身的方法2.2 1.8jdk stream 新特性2.3 Apache的CollectionUtils工具类(推荐)3. 限定泛型范围4. Awakening1. Introduction 1.1 好处 代码复用,多种…...
【Linux】网络编程 - Socket套接字/基于UDP的网络通信
目录 一.套接字 1.什么是套接字/Socket套接字 2.套接字的分类 3.Socket套接字的常见API 二.网络字节序 1.什么是网络字节序 2.网络字节序和主机字节序的转换接口 三.IP地址形式上的转换 四.客户端的套接字不由程序员bind 1.为什么客户端套接字不能由程序员bind 2.OS…...
流程引擎之Camunda简介
背景Camunda 是支持 BPMN(工作流和流程自动化)、CMMN(案例管理) 和 DMN(业务决策管理) java 框架。Camunda 基于Activiti5 保留了 PVM,其开发团队也是从 activiti 中分裂出来的。Camunda 来自拉…...
Mybatis笔记整理
1. 相关文档地址 中文文档 https://mybatis.org/mybatis-3/zh/index.htmlMybatis可以配置成适应多种环境,不过每个SqlSessionFactory实例只能选择一种环境。Mybatis默认事务管理器是JDBC,连接池:POOLEDMaven仓库:下载地址<dependency>…...
【react全家桶】面向组件编程
文章目录02 【面向组件编程】1.组件的使用1.1 函数式组件1.2 类式组件1.3 组合组件1.4 提取组件组件实例的三大属性 state props refs2.state2.1 基本使用2.2 setState()2.3 简化版本2.4 State 的更新可能是异步的2.5 异步更新解决方案2.6 数据是向下流动的3.props3.1 基本使用…...
Django框架之模型视图-使用 PostMan 对请求进行测试
使用 PostMan 对请求进行测试 PostMan 是一款功能强大的网页调试与发送网页 HTTP 请求的 Chrome 插件,可以直接去对我们写出来的路由和视图函数进行调试,作为后端程序员是必须要知道的一个工具。 安装方式1:去 Chrome 商店直接搜索 PostMan…...
(考研湖科大教书匠计算机网络)第五章传输层-第四节:TCP流量控制
获取pdf:密码7281专栏目录首页:【专栏必读】考研湖科大教书匠计算机网络笔记导航 文章目录一:流量控制概述二:流量控制举例三:拓展阅读(可不看)(1)TCP流量控制完整例子&a…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
