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

文章目录

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

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

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

相关文章

安卓小程序与编译抓包

APK小程序渗透测试 查找bp的证书 在浏览器中打开bp代理&#xff0c;然后在网页中搜索hppps://burp 点击高级——接受风险并继续 拿到证书 将浏览器信任证书 打开设置 搜索证书——查看证书 点击导入——导入证书 证书验证成功后&#xff0c;访问网页&#xff08;吾爱破解&a…

模型层——单表操作

单表操作 一 ORM简介 查询数据层次图解&#xff1a;如果操作mysql&#xff0c;ORM是在pymysq之上又进行了一层封装 MVC或者MTV框架中包括一个重要的部分&#xff0c;就是ORM&#xff0c;它实现了数据模型与数据库的解耦&#xff0c;即数据模型的设计不需要依赖于特定的数据库…

河南省第一届职业技能大赛网络安全项目试题

河南省第一届职业技能大赛 网络安全项目试题 一、竞赛时间 总计&#xff1a;420分钟 竞赛阶段 竞赛阶段 任务阶段 竞赛任务 竞赛时间 分值 A模块 A-1 登录安全加固 240分钟 200分 A-2 Web安全加固&#xff08;Web&#xff09; A-3 流量完整性保护与事件监控&am…

韩语语法中에和로/으로区别,柯桥发音入门韩语培训学校

에和로/으로在行动的去向与到达或涉及的地点一致时&#xff0c;二者可以互换。 但是에表示到达或涉及的具体地点&#xff0c;而로/으로表示的时动作指向的方向或经过的地点。 在只表示去向而不表示具体地点时&#xff0c;只能用로/으로&#xff0c;而在只表示具体地点而不表示方…

Nginx漏洞修复

1、漏洞 去掉在请求响应头中存在的信息 Server: nginx X-Content-Type-Options: nosniff X-Frame-Options: SAMEORIGIN X-XSS-Protection: 1;modeblock 修复方法 在Nginx的配置文件中的 server 标签内增加一下配置 server_tokens off; add_header X-Frame-Options SAMEORIGIN; …

情绪咖啡亭完美收官!来最美环湖路喝一杯“治愈”咖啡

“芭比粉”的主题墙&#xff0c;橙蓝撞色的情绪日历、当下最流行的克莱因蓝咖啡亭......颜色鲜艳&#xff0c;造型吸睛的“情绪咖啡亭”互动艺术装置区与碧树蓝天、海鸥白云相呼应。春城晚报&#xff08;开屏新闻&#xff09;生活节“送服务”系列之一的“情绪咖啡亭”活动将在…

jetson nano SSH远程连接(使用MobaXterm)

文章目录 SSH远程连接1.SSH介绍2.准备工作3.连接步骤3.1 IP查询3.2 新建会话和连接 SSH远程连接 本节课的实现&#xff0c;需要将Jetson Nano和电脑保持在同一个局域网内&#xff0c;也就是连接同一个路 由器&#xff0c;通过SSH的方式来实现远程登陆。 1.SSH介绍 SSH是一种网…

字符集与编码规则

字符集 强调&#xff1a;UTF-8是编码规则&#xff0c;不是字符集 过程&#xff1a; 字符 --查表获得对应数字&#xff0c;--编码 解码---查表----获取字符 ASCII码 &#xff1a;一个字节 8bit GBK字符集&#xff08;windows系统默认使用的GBK,系统显示ANSI&#xff09; 存…

segment-anything安装教程

文章目录 一. segment-anything安装教程 一. segment-anything安装教程 官网安装说明:https://github.com/facebookresearch/segment-anything anaconda下新建一个环境 conda create -n sam python3.8激活新建的环境 conda activate sam更换conda镜像源 conda config --add ch…

如何靠掌握自己的大数据打破信息流的壁垒?

在当今数字化时代&#xff0c;打造自己的私域流量已经成为商家乃至获取竞争优势的关键手段之一。通过掌握自己的大数据&#xff0c;可以更好地了解用户需求和市场趋势&#xff0c;优化产品和服务&#xff0c;从而打破信息流的壁垒。本文将就如何通过打造自己的私域流量并掌握大…

ROS URDF集成Rviz流程

实现流程&#xff1a; 一、新建功能包&#xff0c;导入依赖 二、编写 urdf 文件 三、在 launch 文件集成 URDF 与 Rviz 四、在 Rviz 中显示机器人模型 需求&#xff1a;在 Rviz 中显示一个盒状机器人 1、创建功能包&#xff0c;导入依赖 创建一个新的功能包&#xff0c;名…

VMWare17配置自动启动虚拟机提示:无法更新“自动启动配置”,请确保存在vmAutoStart.xml文件,并且您有权写入此文件。

文章目录 配置的时候提示&#xff1a;无法更新“自动启动配置”&#xff0c;请确保存在vmAutoStart.xml文件&#xff0c;并且您有权写入此文件。需要修改vmAutoStart.xml这个文件权限对vmautostart.xml文件右键-->属性&#xff0c;选择编辑直接将完全控制的允许勾上&#xf…

工程师每日刷题 -4

文章目录 1、深度学习2、算法与数据结构2.1、暴力解法2.2、滑动窗口法 3、编程基础 1、深度学习 问题&#xff1a;CNN的本质和优势&#xff1f; CNN 本质上是一个多层感知机 (MLP)&#xff0c;其成功的原因关键在于它所采用的【稀疏连接】&#xff08;局部感受&#xff09;和…

Android Studio Giraffe | 2022.3.1

Android Gradle 插件和 Android Studio 兼容性 Android Studio 构建系统以 Gradle 为基础&#xff0c;并且 Android Gradle 插件 (AGP) 添加了几项专用于构建 Android 应用的功能。下表列出了各个 Android Studio 版本所需的 AGP 版本。 Android Studio 版本所需的 AGP 版本I…

Python+Requests模块session处理和SSL证书处理关闭警告

session处理 部分接口需要先登录网址&#xff0c;才能有权限进行调用&#xff0c;这时可以使用到session&#xff0c;具体操作是&#xff1a;先使用网站 的登录api进行登录&#xff0c;得到session后&#xff0c;然后用该session来请求其它的接口。 示例代码&#xff1a; se…

实验 elk+filebeat+kafka

kafka 3.4.1 elkfilebeatkafka 实现日志收集 httpd1 mysql1 topic 2.7 3.0 关闭防火墙 systemctl stop firewalld systemctl disable firewalld setenforce 0 安装 JDK yum install -y java-1.8.0-openjdk java-1.8.0-openjdk-devel java -version 安装 Zookeeper cd /…

C++作业3

设计一个Per类&#xff0c;类中包含私有成员:姓名、年龄、指针成员身高、体重&#xff0c;再设计一个Stu类&#xff0c;类中包含私有成员:成绩、Per类对象p1&#xff0c;设计这两个类的构造函数、析构函数和拷贝构造函数。 代码&#xff1a; #include <iostream>using n…

力扣5.最长回文子串

题目描述 思路 1.能够反复利用已判断好的回文子串 2.当子串s[i1,j-1]是回文子串时&#xff0c;只要s[i]s[j]&#xff0c;那么s[i,j]也会是回文子串 3.用好动态规划&#xff0c;具体解释在代码注释里 代码 class Solution {public String longestPalindrome(String s) {int…

【【FPGA 之Micro Blaze的串口中断实验】】

FPGA 之Micro Blaze的串口中断实验 我们在使用 MicroBlaze 进行嵌入式系统设计的时候&#xff0c;通常会用到 AXI Uartlite IP 核与外部设备通信。AXI UART IP 核实现了 RS-232 通讯协议&#xff0c;并使得大家可以设置串口通信相关的波特率、奇偶校验位、停止位和数据位等参数…

一看就懂的RxJava源码分析

一看就懂的RxJava源码分析 前言零、观察模式简介一、RxJava使用示例一二、示例一源码分析0. 示例一代码分解1. RxJava中的观察者是谁&#xff1f;2. RxJava中的被观察者又是谁&#xff1f;3. 观察者又是如何安插到被观察者中的&#xff1f;4. 示例一RxJava源码整体关系类图4. R…