leecode 【二】

相交链表

给你两个单链表的头节点 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 中第四个节点) 在内存中指向相同的位置。

 

示例 2:

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

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

自己解的:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       HashMap<ListNode,Boolean> list=new HashMap<>();
       ListNode tmp=headA;
       while(tmp!=null){
           list.put(tmp,true);
           tmp=tmp.next;
       }
       tmp=headB;
       while(tmp!=null&&list.get(tmp)==null){
           tmp=tmp.next;
       }
       return tmp;
    }
}
另一种更优解:

设计代码如下:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

图解参考:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

(数据结构)顺序表的插入删除

#include<stdio.h> #include<stdlib.h> #define MAX 10 typedef struct {int data[MAX];int lenth; }List; //初始化 void CreateList(List* L) {L->lenth 0;for (int i 0; i < MAX; i){L->data[i] 0;} } //插入 int ListInsert(List* L,int i,int e) …

STM32学习笔记--闪存Flash

STM32F1系列的FLASH包含程序存储器、系统存储器和选项字节三个部分&#xff0c;通过闪存存储器接口&#xff08;外设&#xff09;可以对程序存储器和选项字节进行擦除和编程。 读写FLASH的用途&#xff1a;利用程序存储器的剩余空间来保存掉电不丢失的用户数据 &#xff0c;通过…

【数值计算方法(黄明游)】矩阵特征值与特征向量的计算(二):Jacobi 过关法(Jacobi 旋转法的改进)【理论到程序】

文章目录 一、Jacobi 旋转法1. 基本思想2. 注意事项 二、Jacobi 过关法1. 基本思想2. 注意事项 三、Python实现迭代过程&#xff08;调试&#xff09; 矩阵的特征值&#xff08;eigenvalue&#xff09;和特征向量&#xff08;eigenvector&#xff09;在很多应用中都具有重要的数…

Mybatis 的操作(续集)

Mybatis 是一款优秀的 持久性 框架,用于简化 JDBC 的开发 持久层 : 指的就是持久化操作的层,通常指数据访问层(dao),是用来操作数据库的 简单来说 Mybatis 是更简单完成程序和数据库交互的框架 Mybatis 的写法有两种 : 1.xml 2.注解 这两者各有利弊,后面进行总结 Mybati…

matlab 多目标粒子群优化算法MOPSO

1、内容简介 略 21-可以交流、咨询、答疑 多目标、粒子群 2、内容说明 多目标粒子群优化算法MOPSO 3、仿真分析 略 %% Problem Definition TestProblem3; % Set to 1, 2, or 3 switch TestProblem case 1 CostFunction(x) MyCost1(x); nVar5; …

钉钉聊天审计软件有哪些

钉钉在企业中的广泛应用&#xff0c;聊天审计软件也日益受到关注。这类软件主要针对企业微信、钉钉等即时通讯工具&#xff0c;对其中的聊天记录进行审计&#xff0c;以便企业能够更好地管理员工的在线行为&#xff0c;并保障信息安全。 一、聊天审计软件的作用 1、监管员工行…

电子学会C/C++编程等级考试2021年12月(四级)真题解析

C/C++等级考试(1~8级)全部真题・点这里 第1题:移动路线 桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。 小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把…

应用案例 | 基于三维视觉的压缩机装配解决方案

Part.1 压缩机&#xff1a;制冷系统的“心脏” 压缩机是一种将低压气体提升为高压气体的从动的流体机械&#xff0c;被称为制冷系统的“心脏”&#xff0c;是制冷循环的重要动力来源。 作为制冷空调、冷冻设备、汽车空调等各种应用领域中的关键设备&#xff0c;现代压缩机的构造…

【带头学C++】----- 九、类和对象 ---- 9.3 析构函数

9.3 析构函数 9.3.1 如何定义析构函数 函数名和类名称相同&#xff0c;在函数名前加 ~ &#xff0c;没有返回值类型&#xff0c;没有函数形参。 (不能被重载) 当对象生命周期结束的时候&#xff0c;系统自动调用析构函数&#xff08;析构函数会先清理对象占用内存空间存放的…

时间序列预测实战(二十二)TCN-LSTM实现单元和多元长期预测(专为新手编写的自研架构)

一、本文介绍 本篇文章给大家带来的是利用我个人编写的架构进行TCN-LSTM时间序列卷积进行时间序列建模&#xff08;专门为了时间序列领域新人编写的架构&#xff0c;简单不同于市面上用GPT写的代码&#xff09;&#xff0c;包括结果可视化、支持单元预测、多元预测、模型拟合效…

智慧校园:打造未来教育新时代

智慧校园&#xff1a;打造未来教育新时代 智慧校园是指利用先进的信息技术手段&#xff0c;通过云计算、大数据分析、人工智能等技术来提升教育教学质量和管理效率的一种模式。随着科技的不断发展&#xff0c;智慧校园正成为教育领域的热门话题。本文将深入探讨智慧校园的定义、…

附录A 指令集基本原理

1. 引言 本书主要关注指令集体系结构4个主题&#xff1a; 1. 提出对指令集进行分类的方法&#xff0c;并对各种方法的优缺点进行定性评估&#xff1b; 2. 提出并分析一些在很大程度上独立于特定指令集的指令集评估数据。 3. 讨论语言与编译器议题以及…

【渗透】记录阿里云CentOS一次ddos攻击

文章目录 发现防御 发现 防御 流量清洗 使用高防

uni-app 微信小程序 电子签名及签名图片翻转显示功能

文章目录 1. 需求背景2. 开始撸2.1 点击 重写 进入签名页面&#xff08;上图一&#xff09;2.2 书写签名&#xff0c;点击确认返回&#xff0c;及图片翻转显示&#xff08;上图二&#xff0c;三&#xff09; 3. 图片进行翻转&#xff0c;返回翻转后的图片 1. 需求背景 接的一个…

阿里云通义千问720亿参数模型开源,适配企业级、科研级高性能应用

12月1日&#xff0c;阿里云举办通义千问发布会&#xff0c;开源通义千问720亿参数模型Qwen-72B。Qwen-72B在10个权威基准测评创下开源模型最优成绩&#xff0c;成为业界最强开源大模型&#xff0c;性能超越开源标杆Llama 2-70B和大部分商用闭源模型。未来&#xff0c;企业级、科…

windows系统如何配置yarn环境变量

启动前端项目&#xff0c;突然遇到报错&#xff1a; 原因在于没有安装yarn&#xff0c;或没有配置环境变量。 全局安装 yarn 可在vsCode中输入&#xff0c;也可在命令行输入&#xff08;winR&#xff0c;输入cmd&#xff09; npm install -g yarn添加环境变量 找到yarn的安…

scrapy爬虫中间件和下载中间件的使用

一、关于中间件 之前文章说过&#xff0c;scrapy有两种中间件&#xff1a;爬虫中间件和下载中间件&#xff0c;他们的作用时间和位置都不一样&#xff0c;具体区别如下&#xff1a; 爬虫中间件&#xff08;Spider Middleware&#xff09; 作用&#xff1a; 爬虫中间件主要负…

ChatGPT成为“帮凶”:生成虚假数据集支持未知科学假设

ChatGPT 自发布以来&#xff0c;就成为了大家的好帮手&#xff0c;学生党和打工人更是每天都离不开。 然而这次好帮手 ChatGPT 却帮过头了&#xff0c;莫名奇妙的成为了“帮凶”&#xff0c;一位研究人员利用 ChatGPT 创建了虚假的数据集&#xff0c;用来支持未知的科学假设。…

iOS简单理解区分MVC、MVP、MVVM

MVC、MVP、MVVM 前言 这篇文章简单介绍MVC、MVP和MVVM三种架构&#xff0c;并配上一个简单的Swift demo来区分MVC和MVVM两种架构。 MVC 传统MVC 下图是传统结构MVC&#xff0c;可以看到这种结构是紧耦合的&#xff0c;不推荐使用。 苹果的MVC 如下图&#xff0c;这是苹果…