当前位置: 首页 > 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;若大…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...