L7.【LeetCode笔记】相交链表

1.题目

. - 力扣(LeetCode)

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

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

题目数据 保证 整个链式结构中不存在环。

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

自定义评测:

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

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headAheadB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案

示例 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 中第四个节点) 在内存中指向相同的位置。

示例 2:

输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:No intersection
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。

提示:

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listAlistB 没有交点,intersectVal0
  • 如果 listAlistB 有交点,intersectVal == listA[skipA] == listB[skipB]

进阶:你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?

代码模版

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
}

2.自解

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{int length_list1=0;int length_list2=0;struct ListNode* cur1=headA;struct ListNode* cur2=headB;if (cur1==cur2)return cur1;if (headA==NULL||headB==NULL)return NULL;//计算两个链表的节点个数while(cur1){length_list1++;cur1=cur1->next;}while(cur2){length_list2++;cur2=cur2->next;}//恢复cur1和cur2的初值cur1=headA;cur2=headB;if (length_list1==length_list2){while(cur1->next!=cur2->next){cur1=cur1->next;cur2=cur2->next;}return cur1->next;}else if (length_list1>length_list2){int delta_length=length_list1-length_list2;//让长链表先走delta_length步while (delta_length){delta_length--;cur1=cur1->next;}if (cur1==cur2)return cur2;while(cur1->next!=cur2->next){cur1=cur1->next;cur2=cur2->next;}return cur1->next;}else{int delta_length=length_list2-length_list1;//让长链表先走delta_length步while (delta_length){delta_length--;cur2=cur2->next;}if (cur2==cur1)return cur1;while(cur1->next!=cur2->next){cur1=cur1->next;cur2=cur2->next;}cur1=cur1->next;return cur1;}return NULL;
}

几个容易忽视的问题

1.在用cur1和cur2遍历链表后,不要忘记恢复cur1和cur2的初始值

2.headA和headB有一个为NULL,则返回NULL

3.在 while (delta_length)和while(cur1->next!=cur2->next)循环之间有一个if (cur1==cur2) return cur2;  在 while (delta_length)和while(cur1->next!=cur2->next)循环之间也有一个if (cur1==cur2) return cur1;这是应对特殊情况

运行结果

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/9113.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Java开发插件:JRebel热部署(最佳实践+激活方式)

使用场景&#xff1a; 在庞大的项目&#xff0c;我们启动项目的时间较长&#xff0c;尤其每次修改完代码要进行测试&#xff0c;就要重新编译启动项目&#xff0c;耗时且繁琐&#xff0c;热部署插件通过设置更新操作&#xff0c;就可以实现快速启动项目&#xff0c;开发效率显…

2024Python安装与配置IDE汉化集活的全套教程

【一】Python解释器下载【运行环境】 【1】Python官网 包含编程资料、学习路线图、源代码、软件安装包等&#xff01;【[点击这里]】&#xff01; [https://www.python.org]&#xff08;官网进不去的可以点击点击领取&#xff0c;100%免费&#xff01;安装包&#xff09; 【2…

【OD-支持在线评测】数字涂色(100分)

📎 在线评测链接 https://app5938.acapp.acwing.com.cn/contest/11/problem/OD1081 🍓 OJ题目截图 🍿 最新机试E卷,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测,专栏文章质量平均 94 分 🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系解锁~ 文章目录 📎…

JAVA学习接口案例实例

要求&#xff1a; 结果&#xff1a; 测试类&#xff1a; package Z; public class Test {public static void main(String[] args) {ClassMnger p new ClassMnger();p.Students();p.Studentall();p.studentavg();} } 实体数据类 public class ClassAll {//存入班级全部学…

远程连接服务器

1、远程连接服务器 1.1 远程连接服务器------通过文字或图形接口方式来远程登录系统&#xff0c;让你在远程终端前登录linux主机以取得可操 作主机接口&#xff08;shell&#xff09;&#xff0c;而登录后的操作感觉就像是坐在系统前面一样。 1.2 功能------分享主机的运算能…

1分钟教你利用ai工具免费制作10W+情感视频,自动化批量操作,效率提升10倍!

觉得风之馨的文章对你有用的话&#xff0c;记得点赞、关注加星标哦&#xff01; 今天刷到这种人生感悟号,很容易唤起大家的共鸣。转眼间一年即将过去,摸摸口袋没剩下几个钱。内心突然间就伤感起来了&#xff0c;生活不易&#xff0c;且行且珍惜。 评论出大神,有出来拉仇恨的&a…

CISCO产品介绍

思科防火墙是由全球领先的网络解决方案提供商思科&#xff08;Cisco&#xff09;公司研发和生产的一系列网络安全设备。 思科的产品和服务涵盖了多个领域&#xff0c;包括但不限于&#xff1a; 网络硬件&#xff1a;思科的路由器和交换机是其核心产品&#xff0c;广泛应用于企…

Python | Leetcode Python题解之第547题省份数量

题目&#xff1a; 题解&#xff1a; class Solution:def findCircleNum(self, isConnected: List[List[int]]) -> int:def find(index: int) -> int:if parent[index] ! index:parent[index] find(parent[index])return parent[index]def union(index1: int, index2: i…

如何优化Elasticsearch查询以提高性能?

为了优化Elasticsearch查询以提高性能&#xff0c;以下是一些实用的策略和技巧&#xff1a; 节点负载均衡&#xff1a; 通过调整副本数来实现负载均衡。确保分片和副本的总数与节点数量相匹配&#xff0c;以均匀分配查询请求。 慢查询处理&#xff1a; 开启慢查询日志&#xf…

使用SigXplorer进行串扰的仿真

串扰&#xff08;Crosstalk&#xff09;是信号完整性&#xff08;Signal Integrity&#xff09;中的核心问题之一&#xff0c;尤其在当今的高密度电路板设计中&#xff0c;其影响愈发显著。当电路板上的走线密度增大时&#xff0c;各线路间的电磁耦合增强&#xff0c;串扰问题愈…

【报错记录】Steam迁移(移动)游戏报:移动以下应用的内容失败:XXX: 磁盘写入错误

前言 由于黑神话悟空&#xff0c;导致我的2TB的SSD系统盘快满了&#xff0c;我又买了一块4TB的SSD用来存放游戏&#xff0c;我就打算把之前C盘里的游戏移动到D盘&#xff0c;结果Steam移动游戏居然报错了&#xff0c;报的还是“磁盘写入错误”&#xff0c;如下图所示&#xff…

迁移学习相关基础

迁移学习 目标 将某个领域或任务上学习到的知识或模式应用到不同但相关的领域或问题中。 主要思想 从相关领域中迁移标注数据或者知识结构、完成或改进目标领域或任务的学习效果。 概述 Target data&#xff1a;和你的任务有直接关系的数据&#xff0c;但数据量少&#xff…

基于单片机的客车载客状况自动检测系统(论文+源码)

1系统整体设计 本课题为客车载客状况自动检测系统&#xff0c;在此以STM32单片机为核心控制器&#xff0c;结合压力传感器、红外传感器、蜂鸣器、语音提示模块、继电器、液晶等构成整个客车载客状况自动检测系统&#xff0c;整个系统架构如图2.1所示&#xff0c;在此通过两个红…

AscendC从入门到精通系列(一)初步感知AscendC

1 什么是AscendC Ascend C是CANN针对算子开发场景推出的编程语言&#xff0c;原生支持C和C标准规范&#xff0c;兼具开发效率和运行性能。基于Ascend C编写的算子程序&#xff0c;通过编译器编译和运行时调度&#xff0c;运行在昇腾AI处理器上。使用Ascend C&#xff0c;开发者…

生物标记:BCN-PEG-FITC,环丙烷环辛炔聚乙二醇荧光素

在生物标记的舞台上&#xff0c;BCN-PEG-FITC凭借BCN基团的点击化学反应特性&#xff0c;犹如一位技艺高超的舞者&#xff0c;轻盈地在生物分子间穿梭&#xff0c;精准地与其他分子进行标记或探测。这种高特异性的反应&#xff0c;让我们能够更清晰地洞察生命的微观世界。而在分…

C++ 优先算法 —— 三数之和(双指针)

目录 题目&#xff1a;三数之和 1. 题目解析 2. 算法原理 ①. 暴力枚举 ②. 双指针算法 不漏的处理&#xff1a; 去重处理&#xff1a; 固定一个数 a 的优化&#xff1a; 3. 代码实现 Ⅰ. 暴力枚举&#xff08;会超时 O&#xff08;N&#xff09;&#xff09; Ⅱ.…

98_api_intro_websitetools_sslcertinfo

域名 SSL 证书信息解析 API 数据接口 网络工具&#xff0c;提供域名 SSL 证书信息解析&#xff0c;多信息查询&#xff0c;毫秒级响应。 1. 产品功能 提供域名 SSL 证书信息解析&#xff1b;最完整 SSL 属性信息解析&#xff1b;支持多种元素信息抽取&#xff0c;包括主题的可辨…

抓包工具WireShark使用记录

目录 网卡选择&#xff1a; 抓包流程&#xff1a; 捕获过滤器 常用捕获过滤器&#xff1a; 抓包数据的显示 显示过滤器&#xff1a; 常用的显示过滤器&#xff1a; 实际工作中&#xff0c;在平台对接&#xff0c;设备对接等常常需要调试接口&#xff0c;PostMan虽然可以进…

基于单片机的自动充电蓝牙智能台灯的设计

本设计以单片机为主要控制芯片&#xff0c;主要包括主控模块&#xff0c;显示模块&#xff0c;蓝牙模块&#xff0c;ADC转换信号模块&#xff0c;红外感应模块&#xff0c;光敏模块&#xff0c;充电模块等多功能设计。台灯分为自动模式与手动模式&#xff0c;自动模式开启时&am…

猎板 PCB 专业解读:HDI 技术叠构全解

在现代电子制造领域&#xff0c;HDI&#xff08;高密度互连&#xff09;技术占据着举足轻重的地位。其核心亮点在于极具创新性的叠构设计&#xff0c;这一设计使得电子产品在体积上得以大幅缩减&#xff0c;同时性能也获得显著提升。借助精密的盲埋孔连接工艺&#xff0c;HDI 显…