相交链表 - LeetCode 热题 22

大家好!我是曾续缘💤

今天是《LeetCode 热题 100》系列

发车第 22 天

链表第 1 题

❤️点赞 👍 收藏 ⭐再看,养成习惯

相交链表

给你两个单链表的头节点 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
输出:null
解释:从各自的表头开始算起,链表 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) 内存的解决方案?

难度:❤️

解题方法

这道题是关于寻找两个单链表的相交节点的问题。一种常用的解法是使用哈希表来存储其中一个链表的节点,并遍历另一个链表查找是否存在相交节点。

要设计一个时间复杂度为O(m + n)、仅使用O(1)内存空间的解决方案,可以采用双指针法。

首先,计算两个链表的长度,并求出它们的长度差。然后,让较长的链表的指针先移动长度差个节点,使得两个链表剩余的长度相等。接着,同时遍历两个链表,比较它们的节点是否相同,找到相交的节点即可。

Code

/**
 * 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) {
        Set<ListNode> vis = new HashSet<ListNode>();
        ListNode cur = headA;
        while(cur != null){
            vis.add(cur);
            cur = cur.next;
        }
        cur = headB;
        while(cur != null){
            if(vis.contains(cur)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
}

双指针

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        // 计算长度差
        int diff = Math.abs(lenA - lenB);
        
        // 较长链表指针先移动diff个节点
        ListNode curA = headA;
        ListNode curB = headB;
        if (lenA > lenB) {
            for (int i = 0; i < diff; i++) {
                curA = curA.next;
            }
        } else {
            for (int i = 0; i < diff; i++) {
                curB = curB.next;
            }
        }
        
        // 同时遍历两个链表,找到相交节点
        while (curA != null && curB != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        
        return null;
    }
    
    // 计算链表长度
    private int getLength(ListNode head) {
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }
}

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

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

相关文章

CVE-2021-30517:Type confusion bug in LoadSuperIC

前言 这个漏洞是一个比较老的洞&#xff0c;之所以分析这个漏洞&#xff0c;只要是想再学习一下 ICs 相关的知识。并该漏洞的利用是利用与 String/Function 之间的混淆&#xff0c;比较有意思。 环境搭建 sudo apt install python git checkout 7d5e5f6c62c3f38acee12dc4114…

【蓝桥杯第十四届省赛B】(部分详解)

【01串的熵】 https://www.lanqiao.cn/problems/3498/learning/?subject_code1&group_code4&match_num14&match_flow1&origincup #include <iostream> #include<cmath> using namespace std; int main() {double n23333333;double sum0;for(int…

代码学习记录35

随想录日记part35 t i m e &#xff1a; time&#xff1a; time&#xff1a; 2024.04.03 主要内容&#xff1a;今天开始要学习动态规划的相关知识了&#xff0c;今天的内容主要涉及三个方面&#xff1a; 最后一块石头的重量 II &#xff1b;目标和 &#xff1b;一和零 。 1049…

Linux基础篇:文件系统介绍——根目录下文件夹含义与作用介绍

Linux文件系统介绍——文件夹含义与作用 Linux文件系统是一个组织和管理文件的层次结构。它包括了目录、子目录和文件&#xff0c;这些都是按照一定的规则和标准进行组织的。以下是Linux文件系统的一些关键组成部分&#xff1a; 1./bin&#xff1a; 该目录包含了系统启动和运…

抽象类与接口(3)(接口部分)

❤️❤️前言~&#x1f973;&#x1f389;&#x1f389;&#x1f389; hellohello~&#xff0c;大家好&#x1f495;&#x1f495;&#xff0c;这里是E绵绵呀✋✋ &#xff0c;如果觉得这篇文章还不错的话还请点赞❤️❤️收藏&#x1f49e; &#x1f49e; 关注&#x1f4a5;&…

TiDB单机版安装和连接访问

TiDB单机版安装和连接访问 1、下载 $wget http://download.pingcap.org/tidb-latest-linux-amd64.tar.gz 2、解压缩 $tar -zxvf tidb-latest-linux-amd64.tar.gz 3、启动TiDB 启动PD $./bin/pd-server --data-dirpd --log-filepd.log 启动tikv $./bin/tikv-server --pd…

基于深度学习的扑克牌识别软件(网页版+YOLOv8_v7_v6_v5代码+训练数据集)

摘要&#xff1a;本文深入研究了基于YOLOv8/v7/v6/v5的扑克牌识别软件&#xff0c;核心采用YOLOv8并整合了YOLOv7、YOLOv6、YOLOv5算法&#xff0c;进行性能指标对比&#xff1b;详述了国内外研究现状、数据集处理、算法原理、模型构建与训练代码&#xff0c;及基于Streamlit的…

NASA数据集——1983 ——2016 年期间北美森林地点的野外地块特征数据、衍生的地上和地下燃烧碳以及获取的火灾气象指数(FWI)

文件修订日期&#xff1a;2022-05-04 数据集版本: 1 简介 该数据集综合了 1983 年至 2016 年期间美国阿拉斯加、西北地区和加拿大萨斯喀彻温省被烧毁的北方森林地点的野外地块特征数据、衍生的地上和地下燃烧碳以及获取的火灾气象指数&#xff08;FWI&#xff09;系统组件。…

基于 Quartz.NET 可视化任务调度平台 QuartzUI

一、简介 QuartzUI 是基于 Quartz.NET3.0 的定时任务 Web 可视化管理&#xff0c;Docker 打包开箱即用、内置 SQLite 持久化、语言无关、业务代码零污染、支持 RESTful 风格接口、傻瓜式配置、异常请求邮件通知等。 二、部署 QuartzUI 从 2022 年到现在没有提交记录&#xf…

计算机网络:局域网的数据链路层

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

SQLyog连接数据库8.0版本解析错误问题解决方案

问题描述&#xff1a; 解决方案&#xff1a; alter userrootlocalhostidentified with mysql_native_password by 密码; 再次连接就可以了。

Autodesk AutoCAD 2025 (macOS, Windows) - 自动计算机辅助设计软件

Autodesk AutoCAD 2025 (macOS, Windows) - 自动计算机辅助设计软件 AutoCAD 2024 开始原生支持 Apple Silicon&#xff0c;性能提升至 2 倍 请访问原文链接&#xff1a;https://sysin.org/blog/autodesk-autocad/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处…

Express框架搭建项目 node.js

文章目录 引言Express框架介绍express安装环境准备写一个简单的项目展示 文章总结 引言 Express是一个基于Node.js平台的轻量级Web应用框架&#xff0c;它提供了简洁的API和丰富的功能&#xff0c;使得开发者能够快速地构建Web服务器和API。本文将带领大家从零开始&#xff0c…

【初阶数据结构】——leetcode:160. 相交链表

文章目录 1. 题目介绍2. 思路1&#xff1a;暴力求解算法思想代码实现 3. 思路2&#xff1a;快慢指针算法思想代码实现 1. 题目介绍 链接: link 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&…

文件批量重命名管理,一键将图片的名称进行统一重命名,高效管理文件

在数字时代&#xff0c;我们的生活中充满了各种文件&#xff0c;特别是图片文件。随着时间的推移&#xff0c;我们可能会遇到这样的问题&#xff1a;文件命名不规范&#xff0c;难以快速找到需要的图片。这时&#xff0c;一款强大的文件批量重命名管理工具就显得尤为重要。 首…

简约好用的TCPUDP小工具

csdn下载地址&#xff1a; https://download.csdn.net/download/a876106354/89077745

RUST语言流控制语句使用示例

1.判断语句 单条件判断: let mut x128;//声明一个32位整数x512;//修改变量原来的值为新值//如果 ... 否则//判断变量x是否大于256if x>256 {println!("x>256,x{}",x);}else {println!("x<256,x{}",x);}let is_ok:bool true;//rust中不用()if i…

前端三剑客 —— CSS (第三节)

目录 上节回顾&#xff1a; 1.CSS使用有以下几种样式; 2.选择器 1.基本选择器 2.包含选择器 3.属性选择器 [] 4.伪类选择器 &#xff1a; 5.伪元素选择器 ::before :after 3.常见样式的使用 常见样式参考表 一些特殊样式 媒体查询 自定义字体 变换效果 translate&…

2024年湖北中级职称报名时间是什么时候呢?

甘建二十年耕耘职称&#xff0c;关于职称大小事都了解 2024年湖北部分地区职称报名都已经结束了&#xff0c;恩施、十堰、黄冈、黄石、东湖高新上半年、襄阳国企事业单位和副高职称&#xff0c;这些地方的报名都截止了&#xff0c;一年一次&#xff0c;错过了有的没有第二次的话…

基于python的matplotlib库绘制折线图

代码 import matplotlib.pyplot as plt# New data for CIDEr metric beam_sizes [1, 3, 5, 7] CIDEr_new [35.2, 35.6, 38.1, 37.6]# Creating the plot for CIDEr vs Beam Size with the updated data plt.figure(figsize(10, 6)) plt.plot(beam_sizes, CIDEr_new, marker^…