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

力扣刷题TOP101:8.BM10 两个链表的第一个公共结点

目录:

目的

思路

复杂度

记忆秘诀

python代码

目的

两个无环的单向链表,它们的第一个公共结点{{6,7}。


思路

这个任务是找到两个链表的第一个公共结点。可以看作两个心机boy偷偷补课翻车事件。平时嘴上说自己在家玩游戏,实际上背地里都偷偷上各种补习班。小明有一套补习pHead1,小红有一套补习pHead2。他们不仅上完自己的课,还要偷偷上对方的,要卷死对方,但是他们忽略了一点,如果有共同的补习班会再某时候碰上,就要翻车社死了。


心机boys登场:

  • 小明(p1指针):小明有一套自己的补习计划 pHead1,从头到尾按照顺序上课。

  • 小亮(p2指针):小亮则有另一套补习计划 pHead2,也是从头开始按顺序上课。


开始补课

  • 先完成自己的补课计划
    小明和小亮各自按照自己的计划上课p1 = p1.next,p2 = p2.next。

  • 偷偷上对方的课
    当小亮上完所有补习班后,他偷偷跑到小亮的第一个补习班继续补课p1 = pHead2;
    同样,小亮也偷偷跑到小亮 的第一个补习班继续补p2 = p2.next。


翻车时刻

  • 翻车时刻p1 == p2:
    如果有共同的补习班,他们迟早会在这个补习班里翻车碰面社死。这个补习班就是他们的“第一个公共节点”。

    • 为什么一定会翻车?(具体可查看下方数学推导)

      • 因为小明和小亮总会上完整两套补习计划(自己的和对方的),所以只要有相同的补习班,就一定能在第一个相同的课上碰上。
  • 没公共课怎么办
    如果两个计划完全不重合,他们最终都会上完对方的课,开心回家(return p1)。


复杂度

  • 时间复杂度:O(n)

    • 两个心机boy的上课过程相当于遍历两个链表,每个节点最多访问两次,总共为 O(m+n)(m 和 n是链表的长度)即O(n)。
  • 空间复杂度:O(1)

    • 只有两个心机boy(两个指针变量),不多花内存。

记忆秘诀

  • 心机boy上课策略:上自己的补习计划 -> 偷偷上对方的补习计划 -> 碰面社死翻车。

  • 翻车条件:他们最终会在第一个共同的补习班上撞个正着,这就是“第一个公共节点”。如果没公共课,那就各回各家、各找各妈。


补充:数学推导

设定        

  1. 链表A长度为LA,链表B 长度为LB。
  2. 两链表公共部分长度为 LC(第一个公共节点到链表尾部的长度)。
  3. 非公共部分:
    • 链表A的独占部分为 LAbefore = LA - LC。
    • 链表B的独占部分为 LBbefore = LB - LC。

指针P1和P2的移动逻辑:

  1. 指针P1:
    • 从链表 A的头节点出发,依次走完链表 A,然后切换到链表B。
    • 总路径: LAbefore + LC + LBbefore + LC
  2. 指针P2:
    • 从链表B的头节点出发,依次走完链表B,然后切换到链表A。
    • 总路径: LBbefore + LC + LAbefore + LC

总结: 两指针各自遍历两条链表的总路径相等:

          LAbefore + LC + LBbefore + LC = LBbefore + LC + LAbefore + LC

相遇条件:

  1. 当指针P1 和 P2交换链表后:

    • P1进入链表B,P2进入链表A,
    • 由于他们行走的总路径相同,必然会在公共部分 LC的起点(即第一个公共节点)相遇。
  2. 如果两个链表没有公共部分(即 LC=0),两指针最终会同时走到 None,也满足终止条件。

直观解释

  • 两个指针通过在链表间“交叉跑”,平衡了两链表的长度差异。
  • 当两指针的行走路径一致时,自然会在第一个公共节点 C相遇。

python代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:def FindFirstCommonNode(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:if not pHead1 or not pHead2:# 如果有一个补习计划为空,则不可能有共同补习班return None  # 如果其中一个链表为空,则没有公共节点p1 = pHead1 # 小明从pHead1开始p2 = pHead2 # 小亮从pHead2开始# 当小明和小亮没有碰面时,继续上课# 遍历两个链表,直到找到公共节点或者都为Nonewhile p1 != p2:# 如果p1走到末尾,切换到pHead2;否则继续走# 如果小明的课上完了,就转去上小亮的,否则继续上自己的# p1 = p1.next if p1 else pHead2(简写)if p1:  # 如果 p1 不是空p1 = p1.next  # 继续往下走else:  # 如果 p1 是空p1 = pHead2  # 切换到链表2的头节点# 如果p2走到末尾,切换到pHead1;否则继续走# 如果小红的课上完了,就转去上小明,否则继续上自己的# p2 = p2.next if p2 else pHead1(简写)if p2:  # 如果 p2 不是空p2 = p2.next  # 继续往下走else:  # 如果 p2 是空p2 = pHead1  # 切换到链表1的头节点# 相遇点即为第一个公共节点,或者如果没有公共节点则为None# 碰面的补习班(公共节点),或者没有碰面(返回 None)return p1

* 欢迎大家探讨新思路,能够更好的理解和记忆

相关文章:

力扣刷题TOP101:8.BM10 两个链表的第一个公共结点

目录: 目的 思路 复杂度 记忆秘诀 python代码 目的 两个无环的单向链表,它们的第一个公共结点{{6,7}。 思路 这个任务是找到两个链表的第一个公共结点。可以看作两个心机boy偷偷补课翻车事件。平时嘴上说自己在家玩游戏,实际上背地里都偷…...

⽂件操作详解

⽬录 一 文件操作的引入 1 为什么使⽤⽂件? 2 什么是⽂件? 3 文件分类(1 从⽂件功能的⻆度来分类:程序⽂件/数据⽂件 2根据数据的组织形式:为⽂本⽂件/⼆进制⽂件) 二 ⽂件的打开和关闭 1 …...

UR开始打中国牌,重磅发布国产化协作机器人UR7e 和 UR12e

近日,优傲(UR)机器人公司立足中国市场需求,重磅推出UR7e和UR12e 两款本地化协作机器人。它们延续优傲(UR)一以贯之的高品质与性能特质,着重优化负载自重比,且在价格层面具竞争力&…...

PostgreSQL实现透视表查询

PostgreSQL 8.3版本发布时,引入了一个名为tablefunc的新扩展。这个扩展提供了一组非常有趣的函数。其中之一是交叉表函数,用于创建数据透视表。这就是我们将在本文中讨论的内容。 需求说明 解释此函数如何工作的最简单方法是使用带有数据透视表的示例…...

C#里怎么样使用Array.BinarySearch函数?

C#里怎么样使用Array.BinarySearch函数? 因为二分算法如此重要,所以要多加练习。 但是它的返回值,也有三种状态,导致很多人使用它的时候, 也感觉到迷惑的。 在这里的例子演示了三种返回值的使用: /** C# Program to Search an element with Array Indices*/ using …...

量化交易系统开发-实时行情自动化交易-8.5.VNPY平台

19年创业做过一年的量化交易但没有成功,作为交易系统的开发人员积累了一些经验,最近想重新研究交易系统,一边整理一边写出来一些思考供大家参考,也希望跟做量化的朋友有更多的交流和合作。 接下来会对于VNPY平台介绍。 VN.PY 是…...

分治算法中的主定理及其应用

引言 学习递归算法的时候,找到了用来计算算法复杂度的主定理。问大语言模型,发现回答的主定理描述有所不同。本文比较了两个不同版本中表述的差异。并给出一些例子用来计算分治递归类算法的复杂度。 主定理的不同版本 版本1 在《算法导论》第三版第四…...

前端的面试题

1.常用的块与行属性内标签有哪些?有什么特征? 块标签:div、h1~h6、ul、li、table、p、br、form。 特征:独占一行,换行显示,可以设置宽高,可以嵌套块和行 行标签:span、a、img、text…...

vue实现excel导出导入

文章目录 安装xlsx依赖和file-saver依赖Excel导出使用element-ui的el-table展示数据定义导出按钮将数据导出 excel导入定义文件导入显示框定义导入按钮解析选择的文件进行导入 安装xlsx依赖和file-saver依赖 npm install xlsx -S npm install file-saver -SExcel导出 使用ele…...

婚纱摄影管理系统|Java|SSM|VUE| 前后端分离

【重要1⃣️】前后端源码万字文档部署文档 【重要2⃣️】正版源码有问题包售后 【重要3⃣️】虚拟可复制品不支持退换货 【重要3⃣️】虚拟可复制品不支持退换货 【重要3⃣️】虚拟可复制品不支持退换货 【包含内容】 【一】项目提供非常完整的源码注释 【二】相关技术栈文档 【…...

对拍详细使用方法

对拍的作用 对于我们在学校OJ,cf,牛客…各种只提供少量测试数据的题目,常常交上代码常常超时,能写出正确的暴力代码而题目要求的时间复杂度更低。然而这时你写出了能通过样例且时间复杂度更低的代码,但交上去就是错误…...

Flume 与 Kafka 整合实战

目录 一、Kafka 作为 Source【数据进入到kafka中,抽取出来】 (一)环境准备与配置文件创建 (二)创建主题 (三)测试步骤 二、Kafka 作为 Sink数据从别的地方抽取到kafka里面】 (…...

Web开发技术栈选择指南

互联网时代的蓬勃发展,让越来越多人投身软件开发领域。面对前端和后端的选择,很多初学者往往陷入迷茫。让我们一起深入了解这两个领域的特点,帮助你做出最适合自己的选择。 在互联网发展的早期,前端开发主要负责页面布局和简单的…...

社群赋能电商:小程序 AI 智能名片与 S2B2C 商城系统的整合与突破

摘要:本文聚焦于社群在电商领域日益凸显的关键地位,深入探讨在社群粉丝经济迅猛发展背景下,小程序 AI 智能名片与 S2B2C 商城系统如何与社群深度融合,助力电商突破传统运营局限,挖掘新增长点。通过分析社群对电商的价值…...

C++11 http服务端和客户端库cpp-httplib

C11 http服务端和客户端库cpp-httplib 环境: http: yhirose/cpp-httplib v0.18.1 json: nlohmann/json v3.11.31. 简介 cpp-httplib 是一个轻量级且易于使用的 C11 HTTP 库,由 yhirose 开发和维护,开源协议为MIT。它支持 HTTP/HTTPS 协议&…...

spring-boot自定义ApplicationListener及源码分析

ApplicationListener是spring boot应用启动时的事件监听器。监听的事件有&#xff08;包括但不限于&#xff09;&#xff1a; &#xff08;1&#xff09;接下来&#xff0c;我们先通过一个例子实现自定义ApplicationListener&#xff1a; 监听器需要实现ApplicationListener<…...

打造双层环形图:基础与高级渐变效果的应用

在数据可视化领域&#xff0c;环形图因其独特的展示方式而广受欢迎。今天&#xff0c;我们将通过ECharts库来创建一个具有双层渐变效果的高级环形图。本文将详细介绍如何实现这种视觉效果。 1. 环形图基础 首先&#xff0c;我们需要了解环形图的基本构成。环形图由内外两个圆…...

BUGKU printf

整体思路 实现循环-->获取libc版本和system函数地址->将strcpy的got表项修改为system并获得shell 第一步&#xff1a;实现循环 从汇编语句可以看出&#xff0c;在每次循环结束时若0x201700处的值是否大于1则会继续循环。 encode1会将编码后的结果保存至0x2015c0处&am…...

spring boot2.7集成OpenFeign 3.1.7

1.Feign Feign是一个声明式web服务客户端。它使编写web服务客户端更容易。要使用Feign&#xff0c;请创建一个接口并对其进行注释。它具有可插入注释支持&#xff0c;包括Feign注释和JAX-RS注释。Feign还支持可插拔编码器和解码器。Spring Cloud增加了对Spring MVC注释的支持&…...

SSM相关面试题01

目录 1.何为Spring Bean容器?Spring Bean容器与Spring IOC 容器有什么不同吗? 2.Spring IOC 如何理解? 3.Spring DI 如何理解? 4.Spring 中基于注解如何配置对象作用域?以及如何配置延迟加载机制? 5.Spring 工厂底层构建Bean对象借助什么机制?当对象不使用了要释放…...

Python websocket

router.websocket(/chat/{flow_id}) 接口代码&#xff0c;并了解其工作流程、涉及的组件以及如何基于此实现你的新 WebSocket 接口。以下内容将分为几个部分进行讲解&#xff1a; 接口整体概述代码逐行解析关键组件和依赖关系如何基于此实现新功能示例&#xff1a;创建一个新的…...

正则表达式

正则表达式&#xff1a; 正则表达式区别于通配符&#xff0c;正则表达式是用来匹配文本的内容&#xff0c;命令的输出结果也属于文本内容。也可以使用正则表达式。 通配符用来匹配文件名和目录名。 grep用来过滤文本内容&#xff0c;以匹配要查询的结果。 linux的文本三剑客…...

机器学习——生成对抗网络(GANs):原理、进展与应用前景分析

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一. 生成对抗网络的基本原理二. 使用步骤2.1 对抗性训练2.2 损失函数 三. GAN的变种和进展四. 生成对抗网络的应用五. 持续挑战与未来发展方向六. 小结 前言 生…...

HTTPS 加密

HTTPS 加密技术 1. HTTPS 概述 HTTPS&#xff08;HyperText Transfer Protocol Secure&#xff09;是 HTTP 协议的安全版本&#xff0c;利用 SSL/TLS 协议对通信进行加密&#xff0c;确保数据的机密性、完整性和身份认证。HTTPS 在保护敏感数据的传输&#xff08;如登录凭证、…...

Golang 构建学习

Golang 构建学习 如何搭建Golang开发环境 1. 下载GOlang包 https://golang.google.cn/dl/ 在地址上下载Golang 2. 配置包环境 修改全局环境变量&#xff0c;GOPROXY&#xff0c;GOPATH&#xff0c;GOROOT GOPROXYhttps://goproxy.cn,direct GOROOT"" // go二进…...

OpenCV相机标定与3D重建(7)鱼眼镜头立体校正的函数stereoRectify()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 cv::fisheye::stereoRectify 是 OpenCV 中用于鱼眼镜头立体校正的函数。该函数计算两个相机之间的校正变换&#xff0c;使得从两个相机拍摄的图像…...

JVM_垃圾收集器详解

1、 前言 JVM就是Java虚拟机&#xff0c;说白了就是为了屏蔽底层操作系统的不一致而设计出来的一个虚拟机&#xff0c;让用户更加专注上层&#xff0c;而不用在乎下层的一个产品。这就是JVM的跨平台&#xff0c;一次编译&#xff0c;到处运行。 而JVM中的核心功能其实就是自动…...

数据结构4——栈和队列

目录 1.栈 1.1.栈的概念及结构 1.2栈的实现 2.队列 2.1队列的概念及结构 2.2队列的实现 1.栈 1.1.栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一段称为栈顶&#xff0c;另一端称为…...

【AIGC】大模型面试高频考点-数据清洗篇

【AIGC】大模型面试高频考点-数据清洗篇 &#xff08;一&#xff09;常用文本清洗方法1.去除无用的符号2.去除表情符号3.文本只保留汉字4.中文繁体、简体转换5.删除 HTML 标签和特殊字符6.标记化7.小写8.停用词删除9.词干提取和词形还原10.处理缺失数据11.删除重复文本12.处理嘈…...

Java基于SSM框架的跑腿平台小程序【附源码、文档】

博主介绍&#xff1a;✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3…...

数据库连接池

在Java的多线程中&#xff0c;有线程池负责线程管理&#xff0c;类似线程池&#xff0c;在数据库中也有数据库连接池&#xff0c;负责数据库连接的管理。数据库连接池是一个容器。负责分配、管理数据库连接&#xff08;Connection&#xff09;。它允许应用程序重复使用一个现有…...

本地部署 WireGuard 无需公网 IP 实现异地组网

WireGuard 是一个高性能、极简且易于配置的开源虚拟组网协议。使用路由侠内网穿透使其相互通讯。 第一步&#xff0c;服务端&#xff08;假设为公司电脑&#xff09;和客户端&#xff08;假设为公司外的电脑&#xff09;安装部署 WireGuard 1&#xff0c;点此下载&#xff08;…...

Educator头歌:离散数学 - 图论

第1关&#xff1a;图的概念 任务描述 本关任务&#xff1a;学习图的基本概念&#xff0c;完成相关练习。 相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a;图的概念。 图的概念 1.一个图G是一个有序三元组G<V,R,ϕ>&#xff0c;其中V是非空顶点集合&am…...

axios的认识与基本使用

axios简介 Axios 是一个基于 promise 网络请求库&#xff0c;作用于node.js 和浏览器中。 它是 isomorphic 的(即同一套代码可以运行在浏览器和node.js中)。在服务端它使用原生 node.js http 模块, 而在客户端 (浏览端) 则使用 XMLHttpRequests。 主要特点 从浏览器创建 XML…...

springboot358智慧社区居家养老健康管理系统(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 智慧社区居家养老健康管理系统设计与实现 摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&…...

java-a+b 开启java语法学习

代码 &#xff08;ab) import java.util.Scanner; //导入 java.util包中的Scanner 类&#xff0c;允许读取键盘输入数据public class Main { // 创建一个公共类 Mainpublic static void main(String[] args) {//程序入口点&#xff0c;main方法Scanner scanner new Scanner(…...

SpringAi整合免费大模型(NVIDIA)

接上回&#xff0c;发布了springAI整合本地大模型之后&#xff0c;我们来看看怎么去利用别人已经训练好的大模型。 如果对整合本地大模型感兴趣的&#xff0c;请阅读&#xff1a; SpringAI集成本地AI大模型ollama&#xff08;调用篇&#xff09;非常简单&#xff01;&#xf…...

Flutter中的Future和Stream

在 Flutter 中&#xff0c;Future 和 Stream 都是用于处理异步操作的类&#xff0c;它们都基于 Dart 的异步编程模型&#xff0c;但是它们的使用场景和工作方式有所不同。以下是它们的区别以及各自适用的场景。 目录 一、Future1、基本使用2、异常处理1. catchError2. onError…...

Python将Excel文件转换为JSON文件

工作过程中,需要从 Excel 文件中读取数据,然后交给 Python 程序处理数据,中间需要把 Excel 文件读取出来转为 json 格式,再进行下一步数据处理。 这里我们使用pandas库,这是一个强大的数据分析工具,能够方便地读取和处理各种数据格式。需要注意的是还需要引入openpyxl库,…...

MySQL中EXPLAIN的介绍、作用、字段含义

MySQL中EXPLAIN的介绍、作用、字段含义 在MySQL中&#xff0c;EXPLAIN 是一个非常有用的命令&#xff0c;它可以帮助开发者和DBA理解查询执行计划&#xff0c;从而优化查询性能。EXPLAIN 可以模拟优化器执行SQL查询语句&#xff0c;而不真正执行这条语句&#xff0c;从而帮助用…...

Socket编程:UDP网络编程项目

目录 一、回显服务器 二、翻译器 三、聊天室 一、回显服务器 项目介绍&#xff1a;使用UDPIPv4协议进行Linux网络编程&#xff0c;实现回显服务器和客户端 功能介绍&#xff1a;客户端发送数据&#xff0c;经过服务端再返回到客户端&#xff0c;输出数据 源代码&#xff1…...

uniapp echarts tooltip formation 不识别html

需求&#xff1a; echarts 的tooltip 的域名太长&#xff0c;导致超出屏幕 想要让他换行 思路一&#xff1a; 用formation自定义样式实现换行 但是&#xff1a; uniapp 生成微信小程序&#xff0c; echart种的tooltip 的formation 识别不了html &#xff0c;自定义样式没办…...

从0开始linux(39)——线程(2)线程控制

欢迎来到博主的专栏&#xff1a;从0开始linux 博主ID&#xff1a;代码小豪 文章目录 线程创建线程标识符线程参数多线程竞争资源 回收线程detach 线程退出pthread_cancel 线程创建 线程创建的函数为pthread_create。该函数是包含在posix线程库当中&#xff0c;posix线程是C语言…...

对载入的3dtiles进行旋转、平移和缩放变换。

使用 params: {tx: 129.75845, //模型中心X轴坐标&#xff08;经度&#xff0c;单位&#xff1a;十进制度&#xff09;//小左ty: 46.6839, //模型中心Y轴坐标&#xff08;纬度&#xff0c;单位&#xff1a;十进制度&#xff09;//小下tz: 28, //模型中心Z轴坐标&#xff08;高…...

YOLO模型训练后的best.pt和last.pt区别

在选择YOLO模型训练后的权重文件best.pt和last.pt时&#xff0c;主要取决于具体的应用场景‌&#xff1a;‌12 ‌best.pt‌&#xff1a;这个文件保存的是在训练过程中表现最好的模型权重。通常用于推理和部署阶段&#xff0c;因为它包含了在验证集上表现最好的模型权重&#x…...

Qt 项目中同时使用 CMAKE_AUTOUIC 和 UiTools 的注意事项

在 Qt 项目开发中&#xff0c;.ui 文件是界面设计的重要组成部分。开发者可以通过两种主要方式使用 .ui 文件&#xff1a; 编译期处理&#xff1a;通过 Qt 的 uic 工具将 .ui 文件转化为 C 代码&#xff08;ui_xxx.h&#xff09;&#xff0c;静态绑定到项目中。运行时动态加载…...

不玩PS抠图了,改玩Python抠图

网上找了两个苏轼的印章图片&#xff1a; 把这两个印章抠出来的话&#xff0c;对于不少PS高手来说是相当容易&#xff0c;但是要去掉其中的水印&#xff0c;可能要用仿制图章慢慢描绘&#xff0c;图章的边缘也要慢慢勾画或者用通道抠图之类来处理&#xff0c;而且印章的红色也不…...

ubuntu 22.04 mini 安装,在配置网络时重启后配置文件被重置原因与解决方法

在 /etc/netplan/50-cloud-init.yaml 配置文件中有一段注释中有说明 rootlocalhost:/etc/netplan# cat 50-cloud-init.yaml # This file is generated from information provided by the datasource. Changes # to it will not persist across an instance reboot. To disab…...

【Go底层】time包Ticker定时器原理

目录 1、背景2、go版本3、源码解释【1】Ticker结构【2】NewTicker函数解释 4、代码示例5、总结 1、背景 说到定时器我们一般想到的库是cron&#xff0c;但是对于一些简单的定时任务场景&#xff0c;标准库time包下提供的定时器就足够我们使用&#xff0c;本篇文章我们就来研究…...

mac下Gpt Chrome升级成GptBrowser书签和保存的密码恢复

cd /Users/自己的用户名/Library/Application\ Support/ 目录下有 GPT\ Chrome/ Google/ GptBrowser/ GPT\ Chrome 为原来的chrome浏览器的文件存储目录. GptBrowser 为升级后chrome浏览器存储目录 书签所在的文件 Bookmarks 登录账号Login 相关的文件 拷贝到GptBrow…...