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

leetcode_双指针 160.相交链表

news 来源：原创 2025/5/12 6:22:58

160.相交链表

  • 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

  • 思路:

    • 本题中，交点不是数值相等，而是指针相等

    • 双指针遍历两遍后必定相遇，因为它们走过的路径长度相同，最终会在交点相遇

    • 推导:

      假设:：链表 A 长度为 m，即 headA 到 null 的长度。链表 B 长度为 n，即 headB 到 null 的长度。相交部分长度为 c，即交点 intersectNode 到 null 的长度

      headA 到交点的距离为 a，即 m = a + c
      headB 到交点的距离为 b，即 n = b + c

      用等式表示为：

      链表 A 的路径： a + c
      链表 B 的路径： b + c

      • 双指针走的路径
        假设 pointerA 从 headA 开始，pointerB 从 headB 开始：

        第一轮遍历

        pointerA 走过 m（即 a + c）步后到达 null，然后跳到 headB
        pointerB 走过 n（即 b + c）步后到达 null，然后跳到 headA

        第二轮遍历

        pointerA 继续从 headB 走 b 步，此时已到达交点
        pointerB 继续从 headA 走 a 步，此时已到达交点

        也就是说，两个指针在同时走过 a + b + c 步时，同时到达相交点，最终两个指针走过的总步数都是：m + n = (a + c) + (b + c) = a + b + 2c

        由于两者的步数完全相同，它们一定会在第二轮遍历的 c 步处相遇，也就是相交点，反之如果遍历两边后两指针都不相遇，说明不存在交点

    图源https://leetcode.cn/problems/intersection-of-two-linked-lists/description/-

def getIntersectionNode(headA, headB):# 如果链表 A 或者链表 B 为空，直接返回 nullif not headA or not headB:return None# 初始化两个指针pointerA = headApointerB = headB# 当两个指针没有相遇，且都没有遍历完两个链表时while pointerA != pointerB:# 指针 A 遍历完后指向链表 B 的头部，指针 B 遍历完后指向链表 A 的头部pointerA = pointerA.next if pointerA else headBpointerB = pointerB.next if pointerB else headAreturn pointerA  # 如果相交，返回相交的节点；如果没有相交，返回 None
  • 时间复杂度: O(m+n)，每个指针最多只走 m + n 步
  • 空间复杂度: O(1)

相关文章：

leetcode_双指针 160.相交链表

160.相交链表 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 思路: 本题中，交点不是数值相等，而是指针相等 双指针遍历两遍后必定相遇&#xff0c…...

编程日记 2025/5/12 6:22:58

TongSearch3.0.4.0安装和使用指引（by lqw）

文章目录 安装准备手册说明支持的数据类型安装控制台安装单节点(如需集群请跳过这一节)解压和启动开启X-Pack Security和生成p12证书（之后配置内置密码和ssl要用到）配置内置用户密码配置ssl（先配置内置用户密码再配ssl）配置控制台…...

编程日记 2025/5/11 20:34:01

2021.3.1的android studio版本就很好用

使用最新版的studio有个问题就是gradle版本也比较高，这样就容易出现之前项目不兼容问题，配置gradle可能会出现很多问题比较烦，所以干脆就用老版本的studio...

编程日记 2025/5/12 5:20:46

提示词实践总结

目录 一、要求创建SqlServer表（ChatGpt） 二、要求生成多层架构代码（Cursor） 三、要求修改方法返回值类型（Cursor） 四、要求修改方法入参（Cursor） 五、复杂的多表关联生成&#…...

编程日记 2025/5/10 9:51:24

【Elasticsearch】Filters聚合

Filters聚合的基本语法 Filters聚合是一种多桶聚合&#xff0c;用于将文档分组到多个桶中&#xff0c;每个桶对应一个过滤条件。以下是Filters聚合的基本语法和结构&#xff1a; 1.基本结构 json { "aggs": { "<aggregation_name>": { "filter…...

编程日记 2025/5/12 5:59:22

Java基础面试题50题

1&#xff0c;""空字符串的作用 package com.neuedu.nineteen;public class Test {public static void main(String[] args) {String s"";for (char i a; i < d; i) {ssi;//输出abc // sis;//输出cba}System.out.println(s);} }如题所示&…...

编程日记 2025/5/12 4:28:46

Django框架的全面指南：从入门到高级

Django框架的全面指南&#xff1a;从入门到高级 目录 引言Django简介安装与配置创建第一个Django项目Django的MVT架构模型&#xff08;Model&#xff09;视图&#xff08;View&#xff09;模板&#xff08;Template&#xff09;URL路由表单处理用户认证与权限Django Admin高级…...

编程日记 2025/5/12 4:16:54

c++继承

继承的概念和定义 继承的概念 继承 (inheritance) 机制是面向对象程序设计 使代码可以复用 的最重要的手段&#xff0c;它允许程序员在 保 持原有类特性的基础上进行扩展 &#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称派生类。继承 呈现了面向对象 程序设计的…...

编程日记 2025/5/11 9:06:19

【Linux系统】分页式存储管理

分页式存储管理 1、虚拟地址和页表的由来 思考一下&#xff0c;如果在没有虚拟内存和分页机制的情况下&#xff0c;每一个用户程序在物理内存上所对应的空间必须是连续的&#xff0c;如下图&#xff1a; 因为每一个程序的代码、数据长度都是不一样的&#xff0c;按照这样的映射…...

编程日记 2025/5/12 4:47:19

cmd执行mysql命令

安装mysql之后如果想使用cmd执行mysql命令&#xff0c;需要怎么操作呢&#xff0c;下面一起看一下。 安装mysql之后&#xff0c;如果直接去cmd窗口执行MySQL命令&#xff0c;窗口可能会提示mysql不是可执行命令。 需要配置系统的环境变量&#xff0c;将mysql的安装路径配置系…...

编程日记 2025/4/29 12:10:48

第一天：Linux内核架构、文件系统和进程管理

目录 Linux核心概念学习笔记一、Linux内核架构（一）内核的任务（二）实现策略（三）内核的组成部分（四）内核源文件目录结构二、Linux文件系统（一）文件系统架构（二）虚拟文件系统的数据结构三、Linux进程管理（一）进程相关概念（二）进程的层次结构（三）新进程创建机制（…...

编程日记 2025/5/12 6:18:24

QT:信号和槽

目录 1.概念 2.信号和槽的使用 2.1代码的方式使用 2.1.1.使用connect关联 2.2图形化界面的方式使用 2.2.1使用流程 2.2.2使用名字关联槽函数 3.自定义信号和槽函数 3.1自定义槽函数 3.2自定义信号 4.总结 1.概念 信号和槽是QT特有的一种机制&#xff0c;信号和槽都是…...

编程日记 2025/5/10 1:00:35

【Linux系统】线程：认识线程、线程与进程统一理解

一、更新认知 之前的认知 进程&#xff1a;一个执行起来的程序。进程 内核数据结构 代码和数据线程&#xff1a;执行流&#xff0c;执行粒度比进程要更细。是进程内部的一个执行分值 更新认识&#xff1a; a. 进程是承担分配系统资源的基本实体b. 线程是OS调度的基本单位 …...

编程日记 2025/5/12 6:20:46

蓝桥杯字串简写（二分）

输入 4 abababdb a b 输出 6 思路&#xff1a; 如果暴力&#xff0c;o(n**2)&#xff0c;超时&#xff0c;想到可以先与处理一下&#xff0c;记录c1出现的位置&#xff0c;再根据c2的位置用二分法看前面有多少个符合条件的c1。 why二分&#xff1a; 代码&#xff1a;一些…...

编程日记 2025/5/12 4:12:42

【C语言】指针详细解读3

1. 数组名的理解 我们使用指针一般访问数组内容时&#xff0c;我们可能会这样写&#xff1a; int arr[10] {1,2,3,4,5,6,7,8,9,10}; int *p &arr[0]; 这⾥我们使⽤ &arr[0] 的⽅式拿到了数组第⼀个元素的地址&#xff0c;但是其实数组名本来就是地址&#xff0c;⽽…...

编程日记 2025/5/11 18:19:30

Python爬虫-如何正确解决起点中文网的无限debugger

前言 本文是该专栏的第45篇，后面会持续分享python爬虫干货知识，记得关注。 本文以起点中文网为例子，针对起点中文网使用控制台调试出现无限debugger的情况，要如何解决？ 针对该问题，笔者在正文将介绍详细而又轻松的解决方法。废话不多说，下面跟着笔者直接往下看正文详细…...

编程日记 2025/5/12 4:45:06

畅游Diffusion数字人(15)：详细解读字节跳动最新论文——音频+姿态控制人类视频生成OmniHuman-1

Diffusion models代码解读：入门与实战 前言：昨晚字节跳动刚发布了一篇音频+姿态控制人类视频生成OmniHuman-1的论文，效果非常炸裂，并且是基于最新的MM-DiT架构，今天博主详细解读一下这一技术。 目录 贡献概述 方法详解 音频条件注入 Pose条件注入 参考图片条件注入 …...

编程日记 2025/5/11 7:47:18

Windows图形界面(GUI)-QT-C/C++ - QT Dock Widget

公开视频 -> 链接点击跳转公开课程博客首页 -> ​​​链接点击跳转博客主页 目录 一、概述 二、使用场景 1. 工具栏 2. 侧边栏 3. 调试窗口 三、常见样式 1. 停靠位置 2. 浮动窗口 3. 可关闭 4. 可移动 四、属性设置 1. 设置内容 2. 获取内容 3. 设置标题 …...

编程日记 2025/5/12 4:34:18

MIT AppInventor v2.74更新的内容

MIT v2.74更新的内容如下&#xff1a; 新的 UI 选择器提示 向菜单、调色板和设计视图添加键盘导航 更新至 Google Blockly 版本 10 按住 Shift 并拖动以选择多个块 当值被拖近并且没有空闲插槽时&#xff0c;文本等块会自动合并并展开列表 将块拖到边缘时工作区会自动滚动 新的…...

编程日记 2025/5/12 5:48:04

使用 Ollama 在 Windows 环境部署 DeepSeek 大模型实战指南

文章目录 前言Ollama核心特性 实战步骤安装 Ollama验证安装结果部署 DeepSeek 模型拉取模型启动模型 交互体验命令行对话调用 REST API 总结个人简介 前言 近年来&#xff0c;大语言模型&#xff08;LLM&#xff09;的应用逐渐成为技术热点&#xff0c;而 DeepSeek 作为国产开…...

编程日记 2025/5/10 1:01:06

Hackmyvm whitedoor

简介 难度&#xff1a;简单 靶机地址&#xff1a; 环境 kali&#xff1a;192.168.194.9 靶机&#xff1a;192.168.194.24 扫描 nmap -sT -sV -A -T4 192.168.194.24 -p- -Pn 三个服务&#xff0c;ftp匿名登录、ssh连接以及web服务 ftp里面只有一个没用的README文件 访问…...

编程日记 2025/5/12 4:00:45

02/06 软件设计模式

目录 一.创建型模式 抽象工厂 Abstract Factory 构建器 Builder 工厂方法 Factory Method 原型 Prototype 单例模式 Singleton 二.结构型模式 适配器模式 Adapter 桥接模式 Bridge 组合模式 Composite 装饰者模式 Decorator 外观模式 Facade 享元模式 Flyw…...

编程日记 2025/5/12 4:33:16

Java的Integer缓存池

Java的Integer缓冲池&#xff1f; Integer 缓存池主要为了提升性能和节省内存。根据实践发现大部分的数据操作都集中在值比较小的范围&#xff0c;因此缓存这些对象可以减少内存分配和垃圾回收的负担&#xff0c;提升性能。 在-128到 127范围内的 Integer 对象会被缓存和复用…...

编程日记 2025/5/12 5:46:59

[特殊字符] ChatGPT-4与4o大比拼

&#x1f50d; ChatGPT-4与ChatGPT-4o之间有何不同&#xff1f;让我们一探究竟&#xff01; &#x1f680; 性能与速度方面&#xff0c;GPT-4-turbo以其优化设计&#xff0c;提供了更快的响应速度和处理性能&#xff0c;非常适合需要即时反馈的应用场景。相比之下&#xff0c;G…...

编程日记 2025/5/11 6:00:53

2024年12月 Scratch 图形化（二级）真题解析 中国电子学会全国青少年软件编程等级考试

202412 Scratch 图形化&#xff08;二级&#xff09;真题解析 中国电子学会全国青少年软件编程等级考试 一、单选题(共25题&#xff0c;共50分) 第 1 题 小猫初始位置和方向如下图所示&#xff0c;下面哪个选项能让小猫吃到老鼠&#xff1f;&#xff08; &#xff09; A. B. …...

编程日记 2025/5/12 5:00:01

【2025】camunda API接口介绍以及REST接口使用（3）

前言 在前面的两篇文章我们介绍了Camunda的web端和camunda-modeler的使用。这篇文章主要介绍camunda结合springboot进行使用&#xff0c;以及相关api介绍。 该专栏主要为介绍camunda的学习和使用 &#x1f345;【2024】Camunda常用功能基本详细介绍和使用-下&#xff08;1&…...

编程日记 2025/5/12 5:23:03

35.Word：公积金管理中心文员小谢【37】

目录 Word1.docx ​ Word2.docx Word2.docx ​ 注意本套题还是与上一套存在不同之处 Word1.docx 布局样式的应用设计页眉页脚位置在水平/垂直方向上均相对于外边距居中排列&#xff1a;格式→大小对话框→位置→水平/垂直 按下表所列要求将原文中的手动纯文本编号分别替换…...

编程日记 2025/5/11 22:21:02

关于使用numpy进行数据解析性能优化的几点认识

前言&#xff1a;数据解析的性能严重影响用户体验&#xff0c;针对需要批量处理的数据&#xff0c;考虑使用numpy自定义矢量化计算函数提升数据解析的性能。下面的表述都是网上查找的资料&#xff0c;仅供大家参考&#xff0c;具体情况还是需要具体分析的。 1. 使用numpy自定义…...

编程日记 2025/5/12 4:32:04

扣子平台的选择器节点：让智能体开发更简单，扣子免费系列教程（17）

欢迎来到涛涛聊AI。今天&#xff0c;我们来聊聊一个非常实用的工具——扣子平台的选择器节点。即使你不是计算机专业人员&#xff0c;但对计算机操作比较熟悉&#xff0c;这篇文章也能帮你快速上手。我们会从基础知识讲起&#xff0c;一步步带你了解选择器节点的使用方法和应用…...

编程日记 2025/5/5 4:17:01

java s7接收Byte字节，接收word转16位二进制

1图&#xff1a; 2.图&#xff1a; try {List list getNameList();//接收base64S7Connector s7Connector S7ConnectorFactory.buildTCPConnector().withHost("192.168.46.52").withPort(102).withTimeout(1000) //连接超时时间.withRack(0).withSlot(3).build()…...

编程日记 2025/5/11 14:24:44

学习日记250205

一.论文 BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding 二、计划&#xff1a; 理一下微调相关的文章 三. &#xff09;——&#xff08; 明天认真学习了&#xff0c;不能再打这么久的星露谷了&#xff01;&#xff01;&#xff0…...

编程日记 2025/5/10 1:05:04

位置-速度双闭环PID控制详解与C语言实现

目录 概述 1 控制架构解析 1.1 级联控制结构 1.2 性能对比 2 数学模型 2.1 位置环(外环) 2.2 速度环(内环) 3 C语言完整实现 3.1 控制结构体定义 3.2 初始化函数 3.3 双环计算函数 4 参数整定指南 4.1 整定步骤 4.2 典型参数范围 5 关键优化技术 5.1 速度前馈 …...

编程日记 2025/5/12 6:06:17

21.2.1 基本操作

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 Excel的基本操作步骤&#xff1a; 1、打开Excel&#xff1a;定义了一个Application对象&#xff1a; Microsoft.Office.Interop.E…...

编程日记 2025/5/12 6:07:19

Python-基于PyQt5,Pillow,pathilb,imageio,moviepy,sys的GIF(动图)制作工具

前言&#xff1a;在抖音&#xff0c;快手等社交平台上&#xff0c;我们常常见到各种各样的GIF动画。在各大评论区里面&#xff0c;GIF图片以其短小精悍、生动有趣的特点&#xff0c;被广泛用于分享各种有趣的场景、搞笑的瞬间、精彩的动作等&#xff0c;能够快速吸引我们的注意…...

编程日记 2025/5/10 1:06:23

c++ stl 遍历算法和查找算法

概述&#xff1a; 算法主要由头文件<algorithm> <functional> <numeric> 提供 <algorithm> 是所有 STL 头文件中最大的一个&#xff0c;提供了超过 90 个支持各种各样算法的函数&#xff0c;包括排序、合并、搜索、去重、分解、遍历、数值交换、拷贝和…...

编程日记 2025/5/12 6:16:16

Java学习进阶路线

Java基础 Java Web 前端HTML/css/js&#xff0c;J2EE&#xff08;Servlet/jsp&#xff09;&#xff0c;数据库&#xff08;Mysql/oracle&#xff09; Java开发框架 Spring MVC/Mybatis/Herbernate/maven 《Java编程思想》 深入了解java基础 Java设计模式 《Effective j…...

编程日记 2025/5/10 1:05:19

探寻系统响应的奥秘：为何常用以 e 为底的指数组合表示

一、引言 在工程与科学领域的系统分析中&#xff0c;常常会发现系统响应多以 e e e 为底的指数组合来表示。从电路系统里的电流电压变化&#xff0c;到机械系统的振动情况&#xff0c;再到控制系统的动态特性&#xff0c;这种表示方法无处不在。那么&#xff0c;究竟是什么原…...

编程日记 2025/5/10 1:05:51

java 进阶教程_Java进阶教程 第2版

第2版前言 第1版前言 语言基础篇 第1章 Java语言概述 1.1 Java语言简介 1.1.1 Java语言的发展历程 1.1.2 Java的版本历史 1.1.3 Java语言与C&#xff0f;C 1.1.4 Java的特点 1.2 JDK和Java开发环境及工作原理 1.2.1 JDK 1.2.2 Java开发环境 1.2.3 Java工作原理 1.…...

编程日记 2025/5/10 1:05:35

Ext文件系统

文件内容属性 被打开的文件在内存中&#xff0c;没有被打开的文件在磁盘里文件系统的工作就是根据路径帮我们找到在磁盘上的文件 磁盘&#xff08;硬件&#xff09; 磁盘的存储结构 磁头在传动臂的运动下共同进退&#xff0c;向磁盘写入的时候是向柱面批量写入的 OS文件系统访…...

编程日记 2025/5/11 17:12:48

C++滑动窗口技术深度解析：核心原理、高效实现与高阶应用实践

目录 一、滑动窗口的核心原理 二、滑动窗口的两种类型 1. 固定大小的窗口 2. 可变大小的窗口 三、实现细节与关键点 1. 窗口的初始化 2. 窗口的移动策略 3. 结果的更新时机 四、经典问题与代码示例 示例 1&#xff1a;和 ≥ target 的最短子数组&#xff08;可变窗口…...

编程日记 2025/5/9 2:48:33

【HarmonyOS之旅】基于ArkTS开发(三) -＞ 兼容JS的类Web开发(四) -＞ 常见组件(一)

目录 1 -> List 1.1 -> 创建List组件 1.2 -> 添加滚动条 1.3 -> 添加侧边索引栏 1.4 -> 实现列表折叠和展开 1.5 -> 场景示例 2 -> dialog 2.1 -> 创建Dialog组件 2.2 -> 设置弹窗响应 2.3 -> 场景示例 3 -> form 3.1 -> 创建…...

编程日记 2025/5/7 10:55:21

【加餐】使⽤指针实现链表

【加餐】使⽤指针实现链表 ​ 面向过程方式和面向对象方式&#xff08;把面向过程的封装一下就行了&#xff09;是两种不同的编程方法论...

编程日记 2025/4/29 0:15:23

用 Python 绘制爱心形状的简单教程

1. 引言 在本教程中&#xff0c;我们将学习如何使用 Python 和 Matplotlib 库来绘制一个简单的爱心形状。这是一个有趣且简单的项目&#xff0c;适合初学者练习图形绘制和数据可视化。 2. 环境准备 首先&#xff0c;确保您的系统上安装了 Python 和 Matplotlib 库。如果还未…...

编程日记 2025/5/11 3:21:19

DeepSeek安装

安装运行环境 https://ollama.com/ 安装验证 cmd指令 ollama -v 安装运行模型 https://ollama.com/library/deepseek-r1:14b-qwen-distill-q4_K_M 例如&#xff1a; ollama run deepseek-r1:1.5b-qwen-distill-q4_K_M 结果 再次使用时&#xff0c;直接cmd运行上一步的ru…...

编程日记 2025/5/5 2:58:31

Git--使用教程

Git的框架讲解 Git 是一个分布式版本控制系统&#xff0c;其架构设计旨在高效地管理代码版本&#xff0c;支持分布式协作&#xff0c;并确保数据的完整性和安全性。 Git 的核心组件&#xff1a; 工作区&#xff08;Working Directory&#xff09;&#xff1a; - 作区是你在本…...

编程日记 2025/5/11 21:51:20

【HTML性能优化】提升网站加载速度：GZIP、懒加载与资源合并

系列文章目录 01-从零开始学 HTML&#xff1a;构建网页的基本框架与技巧 02-HTML常见文本标签解析&#xff1a;从基础到进阶的全面指南 03-HTML从入门到精通&#xff1a;链接与图像标签全解析 04-HTML 列表标签全解析&#xff1a;无序与有序列表的深度应用 05-HTML表格标签全面…...

编程日记 2025/5/12 4:35:35

C#从XmlDocument提取完整字符串

方法1&#xff1a;通过XmlDocument的OuterXml属性&#xff0c;见XmlDocument类 该方法获得的xml字符串是不带格式的&#xff0c;可读性差 方法2&#xff1a;利用XmlWriterSettings控制格式等一系列参数&#xff0c;见XmlWriterSettings类 例子&#xff1a; using System.IO; …...

编程日记 2025/5/5 5:01:30

wordpress每隔24小时 随机推荐一个指定分类下的置顶内容。

在WordPress中实现每隔24小时随机推荐一个指定分类下的置顶内容&#xff0c;可以通过以下步骤实现&#xff1a; 1. 创建自定义函数 在主题的functions.php文件中添加以下代码&#xff0c;用于创建一个定时任务&#xff0c;每隔24小时随机选择一个置顶文章并存储到选项中&…...

编程日记 2025/5/11 3:32:21

《chatwise：DeepSeek的界面部署》

ChatWise&#xff1a;DeepSeek的界面部署 摘要 本文详细描述了DeepSeek公司针对其核心业务系统进行的界面部署工作。从需求分析到技术实现&#xff0c;再到测试与优化&#xff0c;全面阐述了整个部署过程中的关键步骤和解决方案。通过本文&#xff0c;读者可以深入了解DeepSee…...

编程日记 2025/5/11 20:52:45

HTTP请求响应周期步骤

一个典型的 HTTP 请求/响应周期 从建立连接开始，经过客户端向服务器发送请求、服务器处理请求并返回响应，最终关闭连接。这个过程可以分为多个阶段，以下是详细的步骤： 一、建立连接（TCP连接） 客户端发起连接请求：在HTTP通信中，客户端通常是浏览器，首先通过 DNS 查询…...

编程日记 2025/5/9 22:32:19