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

算法通关村第一关—白银挑战—链表高频面试算法题—查找两个链表的第一个公共子节点

文章目录

  • 查找两个链表的第一个公共子节点
    • (1)暴力求解法
    • (2)使用哈希Hash⭐
    • (3)使用集合⭐ - 与Hash类似
    • (4)使用栈⭐
    • (5)仍有更多方法,作者尚未理解,理解会发出

查找两个链表的第一个公共子节点

  • 原题:Leetcode CR 171. 训练计划 V

题目说明:

输入两个链表,找出它们的第一个公共结点。

在这里插入图片描述
两个链表的头结点都是已知的,相交之后成为一个单链表,但是相交的位置未知,并且相交之前的结点数也是未知的,请设计算法找到两个链表的合并点


(1)暴力求解法

思路:通过冒泡的方式来遍历两个链表,将第一个链表中的每一个结点依次与第二个链表的每一个结点进行比较,当出现相同的结点指针,即为相交结点

注意:该方法虽然简单好理解,但是如果要考虑时间复杂度,暴力求解法一般都是最慢的,耗时最高的

/*** 1.暴力求解,循环遍历两个链表,判断结点相同* @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeByViolence(ListNode headA, ListNode headB) {// 每一个结点进行比较,判断是否相同ListNode A = headA;ListNode B = headB;while (A != null) {while (B != null) {if (A == B) {return A;}B = B.next;}B = headB;A = A.next;}return null;
}

(2)使用哈希Hash⭐

思路:将第一个链表的元素全部存入到HashMap里面,然后一边遍历第二个链表,一边检查当前元素是否在HashMap中

提示:Java中的Map包含containsKey等方法,可以检测该Map中是否包含该元素

在这里插入图片描述

 /*** 2.使用Hash的方法* @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeByMap(ListNode headA, ListNode headB) {Map<ListNode, Integer> hashMap = new HashMap<>();while (headA != null) {hashMap.put(headA, null); // 链表中的所有结点存入HashMap中headA = headA.next;}while (headB != null) {if (hashMap.containsKey(headB)) { // 判断HashMap中是否包含headB,包含说明找到了公共结点,直接返回即可return headB;}headB = headB.next;}return null;
}

(3)使用集合⭐ - 与Hash类似

思路:本质其实和哈希Hash没有太大区别,只是换了一个存储的空间,将所有的结点存入到集合中,然后一边遍历,一边检查当前元素是否在HashSet中

问题:为什么使用Set,而不使用其他集合,如List等等

解释:并不是说不可以使用List集合,相反可以使用List集合,也是可以的,但是List集合的运行时间和第一种暴力求解法没有什么区别,这是由于List集合是有序的,每次存进去其实还会需要记录一个相当于sort排序的值,它第几个进来的,这个也是会占用内存,导致运行时间变长,而Set集合是无序的,不需要记录一个sort值,因此使用Set的速度就快,并且我们追进HashSet的源码进去查看,可以发现HashSet其实就是new HashMap对象,也就是HashSet就是HashMap,跟哈希Hash是没有本质区别的

/*** 3.使用集合的方法* @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {Set<ListNode> set = new HashSet<>();// 循环遍历head1,将head1所有元素存到set中while (headA != null) {set.add(headA);headA = headA.next;}// 循环遍历head2,判断set集合链表是否包含head2while (headB != null) {if (set.contains(headB)) {return headB;}headB = headB.next;}return null;
}

(4)使用栈⭐

思路:将两个链表分别存入到两个栈中,两边同时出栈,判断是否一致,如果一致则说明存在相交,那么我们就继续查找,直到不一致,说明相同的结点都已经出栈了,就已经找到了两个链表的公共结点

提示:栈是后进先出,存进去后相同的都在后面,因此相同的结点也就是存在栈顶

/*** 4.通过栈的方法* @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {Stack<ListNode> stackA = new Stack();Stack<ListNode> stackB = new Stack();while (headA != null) {stackA.push(headA); // 存入栈中headA = headA.next;}while (headB != null) {stackB.push(headB); // 存入栈中headB = headB.next;}ListNode preNode = null;while (stackB.size() > 0 && stackA.size() > 0) {// 由于存是从头存到底部,因此后面的结点都是相同的,当取出来是不一样的时候,说明从公共结点分隔出去了,到分岔口了,那就直接break即可if (stackA.peek() == stackB.peek()) { // peek表示查看此堆栈顶部的对象,但是不会删除,而pop是直接返回了,也就删除了preNode = stackA.pop();stackB.pop();} else {break;}}return preNode;
}

(5)仍有更多方法,作者尚未理解,理解会发出

相关文章:

算法通关村第一关—白银挑战—链表高频面试算法题—查找两个链表的第一个公共子节点

文章目录 查找两个链表的第一个公共子节点&#xff08;1&#xff09;暴力求解法&#xff08;2&#xff09;使用哈希Hash⭐&#xff08;3&#xff09;使用集合⭐ - 与Hash类似&#xff08;4&#xff09;使用栈⭐&#xff08;5&#xff09;仍有更多方法&#xff0c;作者尚未理解&…...

C/C++ 发送与接收HTTP/S请求

HTTP&#xff08;Hypertext Transfer Protocol&#xff09;是一种用于传输超文本的协议。它是一种无状态的、应用层的协议&#xff0c;用于在计算机之间传输超文本文档&#xff0c;通常在 Web 浏览器和 Web 服务器之间进行数据通信。HTTP 是由互联网工程任务组&#xff08;IETF…...

【算法集训】基础数据结构:一、顺序表(下)

由于今天的题目是昨天剩下的&#xff0c;所以只有两道题&#xff0c;也非常简单&#xff0c;刷完下班~~~嘿嘿 第六题 2656. K 个元素的最大和 https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/description/ 很简单的思路&#xff0c;要得到得分最大的&…...

[Java][项目][战斗逻辑]基于JFrame的文字游戏

项目注解&#xff1a; Core:启动文件 AttributeBean&#xff1a;玩家属性 BackpackedBean&#xff1a;背包设计&#xff08;未完成&#xff09; BackpackedFrame&#xff1a;背包页面&#xff08;未完成&#xff09; BattleField&#xff1a;战斗逻辑&#xff08;核心&…...

顺序表和链表面试题

文章目录 顺序表(1)原地移除数组中所有的元素val&#xff0c;要求时间复杂度为O(N)&#xff0c;空间复杂度为O(1)。(2)删除有序数组中的重复项(3)合并两个有序数组 链表(1)删除链表中等于给定值 val 的所有节点(2)反转一个单链表(3) 合并两个有序链表(4)链表的中间结点(5)链表中…...

树_二叉搜索树累加求和

//给出二叉 搜索 树的根节点&#xff0c;该树的节点值各不相同&#xff0c;请你将其转换为累加树&#xff08;Greater Sum Tree&#xff09;&#xff0c;使每个节点 node 的新值等于原树中大于或等于 // node.val 的值之和。 // // 提醒一下&#xff0c;二叉搜索树满足下列约束…...

gcc编译流程概述

前言 本篇文章介绍gcc编译器编译C文件的流程概述 比如我们创建了一个.c文件hello_gcc.c #include <stdio.h> int main() {printf("Hello gcc!!!\n");return 0; }最简单的方式就是在终端使用命令 gcc hello_gcc.c -o hello_gcc // 编译、汇编、链接 ./hello_…...

【web安全】ssrf漏洞的原理与使用

前言 菜某对ssrf漏洞的总结。 ssrf的作用 主要作用&#xff1a;访问外界无法访问的内网进行信息收集。 1.进行端口扫描&#xff0c;资源访问 2.指纹信息识别&#xff0c;访问相应的默认文件 3.利用漏洞或者和payload进一步运行其他程序 4.get类型漏洞利用&#xff0c;传参数…...

佳易王会员管理软件店铺积分以及积分兑换系统

一、佳易王会员管理软件大众版 部分功能简介&#xff1a; 1、会员信息登记 &#xff1a;可以直接使用手机号登记&#xff0c;也可以使用实体卡片&#xff0c;推荐用手机号即可。 2、会员卡类型 &#xff1a;可以自由设置卡的类型&#xff0c;比如&#xff1a;充值卡、计次卡、…...

Django回顾【二】

目录 一、Web框架 二、WSGI协议 三、 Django框架 1、MVC与MTV模型 2、Django的下载与使用 补充 3、启动django项目 补充 5、 Django请求生命周期 四、路由控制 1、路由是什么&#xff1f; 2、如何使用 3、path详细使用 4、re_path详细使用 5、反向解析 6、路由…...

[Ubuntu 18.04] RK3399搭建SSH服务实现远程访问

SSH(Secure Shell)是一种网络协议和软件,用于安全地远程登录到计算机并进行网络服务的加密通信。它提供了加密的认证和安全的数据传输,使得在不安全的网络中进行远程管理和访问变得更加安全。 以下是 SSH 服务的一些关键特点和用途: 安全认证:SSH 使用公钥/私钥加密技术…...

Linux进程间通信之共享内存

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;Linux &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 本博客主要内容讲解共享内存原理和相关接口的介绍&#xff0c;以及一个…...

lv11 嵌入式开发 RTC 17

目录 1 RTC简介 ​编辑2 Exynos4412下的RTC控制器 2.1 概述 2.2 特征 2.3 功能框图 3 寄存器介绍 3.1 概述 3.2 BCD格式的年月日寄存器 3.3 INTP中断挂起寄存器 3.4 RTCCON控制寄存器 3.5 CURTICCNT 作为嘀嗒定时器使用的寄存器 4 RTC编程 5 练习 1 RTC简介 RTC(…...

c语言指针详解(上)

目录 一、指针的基本概念和用法 二、指针运算 2.1 指针的自增和自减运算 2.2 指针的自增和自减运算 三、数组和指针 四、指针和函数 4.1 在函数中使用指针作为参数和返回值 4.1.1 使用指针作为函数参数 4.1.2 使用指针作为函数返回值 4.2 指针参数的传值和传引用特性 4.2.1 指针…...

如何删除mac苹果电脑上面的流氓软件?

在使用苹果电脑的过程中&#xff0c;有时候我们也会遇到一些不需要的软件。无论是因为不再需要&#xff0c;或者是为了释放磁盘空间&#xff0c;删除这些软件是很重要的。本文将为大家介绍怎样删除苹果电脑上的软件&#xff01; CleanMyMac X全新版下载如下: https://wm.make…...

WordPress(11)给文章添加预计阅读时长

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、文件配置二、代码块1.引入库2.配置 single.php三、效果图前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了…...

周周爱学习之快速排序

快速排序&#xff0c;顾名思义&#xff0c;快速排序是一种速度非常快的一种排序算法 平均时间复杂度为O(),最坏时间复杂度为O()数据量较大时&#xff0c;优势非常明显属于不稳定排序 1.算法描述 每一轮排序选择一个基准点&#xff08;pivot&#xff09;进行分区 让小于基准点…...

国产接口测试工具APIpost

说实话&#xff0c;了解APIpost是因为&#xff0c;我的所有接口相关的文章下&#xff0c;都有该APIpost水军的评论&#xff0c;无非就是APIpost是中文版的postman&#xff0c;有多么多么好用&#xff0c;虽然咱也还不是什么啥网红&#xff0c;但是不知会一声就乱在评论区打广告…...

MySQL电商管理系统练习题及答案

一 、表结构 用户表(user)&#xff1a;id(主键)、username、password、email、phone、age商品表(product)&#xff1a;id(主键)、name、price、stock、description订单表(order)&#xff1a;id(主键)、user_id(外键&#xff0c;关联用户表)、total_price、status、create_time…...

每日3道PWN(第二天)

ciscn_2019_n_1 参考&#xff1a; [BUUCTF-pwn]——ciscn_2019_n_1-CSDN博客 [BUUCTF]PWN5——ciscn_2019_n_1_ciscn_2019_n_4-CSDN博客 BUUCTF—ciscn_2019_n_1 1-CSDN博客 checksec一下 64位栈溢出 按f5查看main函数&#xff0c;双击可疑函数 发现含有命令执行的且发现fl…...

RevokeMsgPatcher深度解析:二进制补丁技术如何永久保存即时通讯消息

RevokeMsgPatcher深度解析&#xff1a;二进制补丁技术如何永久保存即时通讯消息 【免费下载链接】RevokeMsgPatcher :trollface: A hex editor for WeChat/QQ/TIM - PC版微信/QQ/TIM防撤回补丁&#xff08;我已经看到了&#xff0c;撤回也没用了&#xff09; 项目地址: https…...

如何快速激活Cursor Pro:免费VIP完整教程与破解工具详解

如何快速激活Cursor Pro&#xff1a;免费VIP完整教程与破解工具详解 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached your t…...

【专栏一:AI基础01】-【一张图讲清楚什么是大模型】

专栏一&#xff1a;AI基础入门-什么是大模型&#xff1f;大模型通俗解释大模型通俗解释 我们可以把大模型想象成一个超级大脑&#xff1a; 它在诞生之初&#xff0c;会先阅读人类海量的文字、知识、书籍、网页、对话&#xff0c;把所有信息消化成一套庞大的数学规律和语言逻辑&…...

Java突变测试终极指南:Pitest如何提升你的代码质量

Java突变测试终极指南&#xff1a;Pitest如何提升你的代码质量 【免费下载链接】pitest State of the art mutation testing system for the JVM 项目地址: https://gitcode.com/gh_mirrors/pi/pitest 突变测试是Java开发中革命性的质量保障技术&#xff0c;而Pitest&am…...

革新性开源工具Win11Debloat:突破Windows 11性能瓶颈的系统优化方案

革新性开源工具Win11Debloat&#xff1a;突破Windows 11性能瓶颈的系统优化方案 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本&#xff0c;用于从Windows中移除预装的无用软件&#xff0c;禁用遥测&#xff0c;从Windows搜索中移除Bing&#xff0c;以及执行各种其他…...

C++笔记 缺省值 函数重载 名字空间域(基础核心)

本文为C基础核心知识点笔记&#xff0c;聚焦「缺省值」「函数重载&#xff08;概念&#xff09;」「名字空间域」三大高频基础考点&#xff0c;语言通俗、重点突出&#xff0c;兼顾入门理解和考试记忆&#xff0c;适合新手入门、作业复习及GitHub归档。一、缺省值&#xff08;默…...

从游戏到医疗:用Touch™和OpenHaptics 3.5解锁Windows力反馈应用新场景(附Unity与C++双环境配置要点)

从游戏到医疗&#xff1a;Touch™力反馈技术的跨界应用与开发实践 想象一下&#xff0c;外科医生在虚拟手术训练中感受到真实的组织阻力&#xff0c;汽车维修学员通过触觉反馈"触摸"到发动机零件的磨损痕迹&#xff0c;游戏玩家在射击游戏中体验到不同武器的后坐力差…...

杰理之数字MIC使用补充【篇】

SFR(JL_ASS->CLK_CON, 0, 2, 3);...

树莓派Pico RP2040 I2C实战:用AT24C02 EEPROM做个数据掉电保存的小项目

树莓派Pico RP2040 I2C实战&#xff1a;用AT24C02 EEPROM实现数据持久化存储 在嵌入式开发中&#xff0c;数据持久化存储是一个常见需求。当我们需要保存设备配置、运行日志或用户设置时&#xff0c;EEPROM&#xff08;电可擦可编程只读存储器&#xff09;因其非易失性特性成为…...

QWen 3.5plus总结的总结基准测试结果的正确方法

原文地址&#xff1a;https://dl.acm.org/doi/epdf/10.1145/5666.5673 如何用统计撒谎&#xff1a;总结基准测试结果的正确方法 作者&#xff1a;PHILIP J. FLEMING 和 JOHN J. WALLACE 在文献中&#xff0c;性能结果经常使用性能比率的算术平均值来总结&#xff0c;在某些情况…...