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

leetcode160. 相交链表

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

图示两个链表在节点 c1 开始相交:

在这里插入图片描述
题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

示例 1:

在这里插入图片描述
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at ‘8’
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

思路:
两个指针分别指向两个链表表头,依次遍历判断两个指针指向的结点是否相等,若一方结点走到末尾为空后,指向另一个链表的头结点接着遍历比较,经过数学分析最多遍历m+n次,即可获得相交结点或者不存在相交结点。

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {if (headA == nullptr || headB == nullptr)return nullptr;ListNode* pa = headA;ListNode* pb = headB;while (pa != nullptr || pb != nullptr)//走的次数一样 所以最后都停在nullptr{if (pa == pb)return pa;//判断是否相同 相同代表有交点if (pa == nullptr)pa = headB;elsepa = pa->next;//每次pa只移动一次 if (pb == nullptr)pb = headA;else pb = pb->next;//每轮pb只移动一次}return nullptr;//没有交点
}
int main() {ListNode node1, node2, node3, node4, node5, node6, node7, node8;node1.val = 4;node1.next = &node2;node2.val = 1;node2.next = &node3;node3.val = 8;node3.next = &node4;node4.val = 4;node4.next = &node5;node5.val = 5;node5.next = nullptr;node6.val = 5;node6.next = &node7;node7.val = 6;node7.next = &node8;node8.val = 1;node8.next = &node3;ListNode* res = getIntersectionNode(&node1, &node6);if (res){cout << res->val << endl;}else {cout << "no intersection node" << endl;}return 0;
}

相关文章:

leetcode160. 相交链表

给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;函数返回结果后&…...

核心业务7:放款实现

核心业务7:放款实现 1.放款实现流程 -------------------未完成生成借款人还款计划和投资人回款计划-------------- 2.数据库表 3.前端流程 4.汇付宝流程 5.尚融宝后端流程 -------------------未完成生成借款人还款计划和投资人回款计划-------------- -------------…...

STM32F4系列芯片RTC模块介绍

RTC是“实时时钟”的缩写&#xff0c;它是一种芯片&#xff0c;在计算机等电子产品中广泛应用。RTC提供了实时时钟计时功能和存储时间的能力&#xff0c;即时钟模块&#xff0c;常用于控制和记录时间的应用场合。 RTC的工作原理 RTC主要由时钟电路、电源管理电路、晶振电路、…...

MySQL 在线人数 场景分析

一般在直播或者游戏中经常会统计用户在线人数&#xff0c;主要分为求每个时刻的在线人数和求某个时刻的在线人数两种。 【场景】&#xff1a;某个时刻的在线人数、每个时刻的在线人数 【知识点】&#xff1a;窗口函数、时间函数、sum(tag) over (order by dt,tag desc rows b…...

使用mybatis和dynamic-datasource-spring-boot-starter动态切换数据源操作数据库

记录&#xff1a;415 场景&#xff1a;使用mybatis和dynamic-datasource-spring-boot-starter动态切换数据源操作数据库。 版本&#xff1a;JDK 1.8,Spring Boot 2.6.3,dynamic-datasource-spring-boot-starter-3.3.2,mybatis-3.5.9。 源码&#xff1a;https://github.com/b…...

【日常刷题】迷宫问题

描述 定义一个二维数组 N*M &#xff0c;如 5 5 数组下所示&#xff1a; int maze[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫&#xff0c;其中的1表示墙壁&#xff0c;0表示可以走的路&#xff0c;只能横着走…...

【Python童年游戏】满满的回忆杀—那些年玩过的童年游戏你还记得吗?那个才是你的菜?看到第一个我就泪奔了(致我们逝去的青春)

导语 滴一一学生卡&#x1f64c; 结伴上车的学生仔子们 用笑声打破车厢的沉默 大人眼里的晚高峰 是给放学后快乐&#x1f600;时光的加时 下车的学生匆匆起身带起 一阵熟悉的栀子香于&#x1f493; 是关于校园的记忆 开始零零散散地闪现 放学后集合的秘密基地/跟着城…...

C++ | 认识标准库string和vector

本文概要 本篇文章主要介绍C的标准库类型string和vector&#xff0c;文中描述和代码示例很详细&#xff0c;看完即可掌握&#xff0c;感兴趣的小伙伴快来一起学习吧。 &#x1f31f;&#x1f31f;&#x1f31f;个人简介 &#x1f31f;&#x1f31f;&#x1f31f; ☀️大家好&a…...

JAVA面试宝典: SpringCloud知识点(通俗易懂易背)

1、什么是 Spring Cloud&#xff1f; Spring Cloud 是基于 Spring Boot 的微服务架构开发工具箱&#xff0c;提供了在分布式系统中构建可靠的、弹性的、灵活的应用所需的大多数工具。Spring Cloud 中包含的子项目如下&#xff1a; Spring Cloud Config&#xff1a;配置管理工具…...

es学习笔记

集群环境下数据往哪个节点放? 路由计算&#xff1a;hash(id) %主分片的数量 集群环境下查数据怎么查&#xff1f; 分配控制&#xff1a;访问任何一个节点都能获取数据&#xff0c;随机访问到的这个节点称为协调节点&#xff08;访问了当前节点&#xff0c;不一定从当前节点…...

SAS学习第9章:卡方检验之适合性检验与独立性检验

卡方检验就是统计样本的实际观测值与理论推断值之间的偏离程度&#xff0c;实际观测值与理论推断值之间的偏离程度就决定卡方值的大小&#xff0c;如果卡方值越大&#xff0c;二者偏差程度越大&#xff1b;反之&#xff0c;二者偏差越小&#xff1b;若两个值完全相等时&#xf…...

马斯克爆料Twitter裁了八成员工;OpenAI CEO:GPT-5根本不存在;小鹏被曝年终奖打0.5折 | AI一周资讯

来源: AI前线 微信号&#xff1a;ai-front 整理 | 凌敏 微软宣布开源 Deep Speed Chat&#xff1b;消息称软银旗下 Arm 启动赴美 IPO&#xff1b;国家网信办出台生成式 AI 管理办法&#xff1b;前理想 AI 芯片一号位骄旸加入三星&#xff0c;负责组建 GPU 团队…… 资 讯 Op…...

ASEMI代理ADG1408YRUZ-REEL7原装ADI车规级ADG1408YRUZ-REEL7

编辑&#xff1a;ll ASEMI代理ADG1408YRUZ-REEL7原装ADI车规级ADG1408YRUZ-REEL7 型号&#xff1a;ADG1408YRUZ-REEL7 品牌&#xff1a;ADI /亚德诺 封装&#xff1a;TSSOP-16 批号&#xff1a;2023 安装类型&#xff1a;表面贴装型 引脚数量&#xff1a;16 类型&#…...

phpstudy本地环境搭建图文教程

作者&#xff1a;Eason_LYC 悲观者预言失败&#xff0c;十言九中。 乐观者创造奇迹&#xff0c;一次即可。 一个人的价值&#xff0c;在于他所拥有的。可以不学无术&#xff0c;但不能一无所有&#xff01; 技术领域&#xff1a;WEB安全、网络攻防 关注WEB安全、网络攻防。我的…...

【UE 控件蓝图】菜单及功能实现

素材资源连接&#xff1a;百度网盘 请输入提取码 密码&#xff1a;fvcw 效果 步骤 1. 创建蓝图&#xff0c;父类为“HUD” 命名为“MainMenuHUD”并打开 在事件图表中添加如下节点&#xff1a; 2. 创建控件蓝图&#xff0c;命名为“MainMenuWidget” 此时在“MainMenuHUD”的…...

Java 并发编程面试题——Future

目录 1.什么是 Future 模式&#xff1f;Java 中是如何实现的&#xff1f;2.Callable、Future 与 FutureTask 分别是什么&#xff1f;2.1.Callable 接口2.2.Future 接口2.3.FutureTask 类 3.CompletableFuture 类有什么用&#xff1f; 1.什么是 Future 模式&#xff1f;Java 中是…...

SpringBoot 介绍

1.简介 SpringBoot最开始基于Spring4.0设计&#xff0c;是由Pivotal公司提供的框架。 SpringBoot发展史&#xff1a; 2003年Rod Johnson成立Interface公司&#xff0c;产品是SpringFramework2004年&#xff0c;Spring框架开源&#xff0c;公司改名为Spring Source2008年&…...

自动驾驶作业手册

1 总 则 目的为保障港口内自动驾驶车辆安全使用,预防和减少事故,保护人民生命和财产安全,促进港口内业务开展。 含义和范围港口内自动驾驶车辆,是指电脑驾驶车辆,为一种运输动力的无人地面载具,与有人驾驶车辆不同,其具备不需要人类操作即可以感测其环境及导航功能,能…...

MySQL调优笔记——慢SQL优化记录(2)

今天调优的原因是&#xff0c;有一个统计报表业务&#xff0c;查询的时间太慢&#xff1b;同时由于数据库的压力是随机性的&#xff0c;这个业务的执行下限和上限相差近20倍&#xff1b;快的时候可以达到600ms&#xff0c;慢的时候有9秒之多&#xff1b; 接下来详细介绍&#x…...

二叉排序树的插入和删除操作(python实现)

二叉排序树的插入和删除操作都是在保持二叉排序树特性的前提下进行的。 插入操作&#xff1a; 在二叉排序树中插入一个新节点时&#xff0c;先比较新节点的值和当前节点的值的大小关系&#xff0c;若小于当前节点&#xff0c;则继续在当前节点的左子树中查找&#xff1b;若大…...

antd vue表单实战:getFieldDecorator、getFieldValue、setFieldValue保姆级教程

Ant Design Vue 表单开发深度指南&#xff1a;数据绑定与动态操作实战 在当今前端开发领域&#xff0c;表单处理一直是构建交互式应用的核心挑战之一。Ant Design Vue 作为企业级 UI 设计语言和 React 实现&#xff0c;提供了一套强大而灵活的表单解决方案&#xff0c;特别适合…...

Claude浏览器扩展漏洞允许通过任意网站实现零点击XSS提示注入

网络安全研究人员披露了Anthropic公司Claude谷歌浏览器扩展中存在的一个漏洞&#xff0c;攻击者只需诱使用户访问特定网页即可触发恶意提示注入。漏洞原理分析Koi Security研究员Oren Yomtov在提供给The Hacker News的报告中指出&#xff1a;"该漏洞允许任何网站静默地向该…...

MIB2 High Toolbox:重新定义车载娱乐系统定制体验

MIB2 High Toolbox&#xff1a;重新定义车载娱乐系统定制体验 【免费下载链接】mib2-toolbox The ultimate MIB2-HIGH toolbox. 项目地址: https://gitcode.com/gh_mirrors/mi/mib2-toolbox 车载娱乐系统是否还停留在出厂设置&#xff1f;想要个性化界面却苦于没有工具&…...

告别bypy上传失败!用Aria2+百度云直链脚本,让服务器下载速度飙升5倍

告别bypy上传失败&#xff01;用Aria2百度云直链脚本&#xff0c;让服务器下载速度飙升5倍 如果你经常需要将百度网盘中的大文件&#xff08;比如几十GB的机器学习模型或数据集&#xff09;传输到服务器上&#xff0c;一定对bypy的种种限制深有体会——速度慢、不稳定、大文件容…...

OpenArk:新一代Windows系统安全分析工具完整指南

OpenArk&#xff1a;新一代Windows系统安全分析工具完整指南 【免费下载链接】OpenArk The Next Generation of Anti-Rookit(ARK) tool for Windows. 项目地址: https://gitcode.com/GitHub_Trending/op/OpenArk 如果你正在寻找一款强大的Windows系统安全分析工具&#…...

iBeebo:5个理由让你选择这款纯净高效的第三方微博客户端

iBeebo&#xff1a;5个理由让你选择这款纯净高效的第三方微博客户端 【免费下载链接】iBeebo 第三方新浪微博客户端 项目地址: https://gitcode.com/gh_mirrors/ib/iBeebo 在信息过载的数字时代&#xff0c;官方微博客户端日益臃肿的界面设计、无处不在的广告推送和复杂…...

告别‘缺少DLL’:用EnigmaVB给Qt5.14程序封包的保姆级避坑指南

告别“缺少DLL”困境&#xff1a;EnigmaVBQt5.14封包全流程实战手册 当你用Qt Creator完成开发&#xff0c;满怀期待地将程序打包发给用户&#xff0c;却收到“缺少xxx.dll”的报错反馈时&#xff0c;这种挫败感开发者都深有体会。本文将以Qt5.14为例&#xff0c;结合EnigmaVB封…...

MySQL视图实战:用SQL视图搞定学生奖学金评定与补考名单(附完整代码)

MySQL视图实战&#xff1a;用SQL视图搞定学生奖学金评定与补考名单&#xff08;附完整代码&#xff09; 教务管理系统中&#xff0c;数据处理效率直接影响决策质量。想象一下每学期末&#xff0c;教务处老师需要从数十万条记录中筛选奖学金候选人和补考名单——传统的手写SQL查…...

终极免费EVE舰船配置神器:Pyfa完整实战指南

终极免费EVE舰船配置神器&#xff1a;Pyfa完整实战指南 【免费下载链接】Pyfa Python fitting assistant, cross-platform fitting tool for EVE Online 项目地址: https://gitcode.com/gh_mirrors/py/Pyfa 在EVE Online这个充满挑战的宇宙中&#xff0c;打造一艘完美的…...

Qt与MongoDB的C++实战:从基础连接到图像数据存储

1. 为什么选择Qt与MongoDB组合 在开发需要处理大量非结构化数据的应用时&#xff0c;传统关系型数据库往往会遇到性能瓶颈。我曾经在一个智能安防项目中&#xff0c;需要存储和分析数万张人脸识别图片&#xff0c;正是这个需求让我深入研究了Qt与MongoDB的组合方案。 MongoDB作…...