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

本文主要是介绍算法通关村第一关—白银挑战—链表高频面试算法题—查找两个链表的第一个公共子节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 查找两个链表的第一个公共子节点
    • (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)仍有更多方法,作者尚未理解,理解会发出

这篇关于算法通关村第一关—白银挑战—链表高频面试算法题—查找两个链表的第一个公共子节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/446618

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

java两个List的交集,并集方式

《java两个List的交集,并集方式》文章主要介绍了Java中两个List的交集和并集的处理方法,推荐使用Apache的CollectionUtils工具类,因为它简单且不会改变原有集合,同时,文章... 目录Java两个List的交集,并集方法一方法二方法三总结java两个List的交集,并集方法一

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1