数据结构入门到入土——链表(2)

目录

一,与链表相关的题目(2)

1.输入两个链表,找出它们的第一个公共节点

2.给定一个链表,判断链表中是否有环

3.给定一个链表,返回链表开始入环的第一个节点,若无则返回null


一,与链表相关的题目(2)

1.输入两个链表,找出它们的第一个公共节点

下面是两个相交的链表

此时要找两个链表的相交节点非常简单

只需要将两个链表的头节点分别向后移

当head1 == head2 时说明改节点是它们的相交节点

但当两个链表长度不一样的时候就会出现问题

遇到这种情况,一般会先求出两个链表的长度len1与len2,让长的那个链表走两链表的差值步(len1-len2)/(len2 - len1)

之后走相同步数直至相遇

代码示例:

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode cur1 = headA;ListNode cur2 = headB;int count1 = 0;int count2 = 0;while (cur1.next != null) {count1++;cur1 = cur1.next;}cur1 = headA;while (cur2.next != null) {count2++;cur2 = cur2.next;}cur2 = headB;int dif = 0;if (count1 >= count2) {dif = count1 - count2;while (dif != 0) {cur1 = cur1.next;dif--;}} else {dif = count2 - count1;while (dif != 0) {cur2 = cur2.next;dif--;}}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}if (cur1 == cur2) {return cur1;} else {return null;}}}

2.给定一个链表,判断链表中是否有环

【思路】
       快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。比如:陪女朋友到操作跑步减肥。
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {return true;}}return false;}}
为什么快指针每次走两步,慢指针走一步可以?
假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在慢指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。

3.给定一个链表,返回链表开始入环的第一个节点,若无则返回null

上一题我们知道了怎么求一个链表是否有环,而其实这一题也不难。基于上一题的基础上,我们给出以下推导:
通过以上过程我们推导出头节点距入口处(x)其实是等于快指针和慢指针相遇点到入口处的距离(y)的,所有我们大可在这里再次令slow等于head,让fast和slow以相同的速度往后走,因为速度一样,路程一样,所有它们再次相遇的地方就一定是这个环的入口点
这里是当fast只比slow多走一圈的情况
而还存在的情况就是当环很小,而head距入口处又非常远时,fast就会为了等待x进入环而多走n圈
此时我们还可以根据上一题的思路就可以推导出以下公式:
详解:
可以发现,slow到入口点的距离(x)其实是等于转的圈数减一乘以圈的周长,再加上slow和fast的相遇点距入口点的距离(y)的,并且我们上一题的推导结果也符合该条公式。
此时代码就可以基于上一题的代码进行修改并书写:
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return fast;}}return null;}}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

09、docker 安装nacos并配置mysql存储配置信息

docker 安装nacos并配置mysql存储配置信息 1、docker启动nacos的各种方式2、Docker安装nacos3、MySQL中新建nacos的数据库4、挂载数据or配置目录5、运行 1、docker启动nacos的各种方式 内嵌derby数据源 docker run -d \ -e PREFER_HOST_MODEhostname \ -e SPRING_DATASOURCE_…

计算机毕业论文内容参考|基于智能搜索引擎的图书管理系统的设计与实现

文章目录 摘要前言绪论课题背景国内外现状与趋势课题内容相关技术与方法介绍系统分析系统设计系统实现系统测试总结与展望摘要 本文介绍了基于智能搜索引擎的图书管理系统的设计与实现。该系统旨在提供一个高效、智能化的图书管理平台,帮助用户更快、更准确地找到所需的图书资…

XCTF-Misc1 USB键盘流量分析

m0_01 附件是一个USB流量文件 分析 1.键盘流量 USB协议数据部分在Leftover Capture Data域中,数据长度为八个字节,其中键盘击健信息集中在第三个字节中。 usb keyboard映射表:USB协议中HID设备描述符以及键盘按键值对应编码表 2.USB…

Java:Stream流

文章目录 1、体验Stream流2、Stream流的常见生成方式3、Stream流中间操作方法4、Stream流终结操作方法5、Stream流的收集操作6、Stream流综合练习6.1 练习16.2 练习26.3 练习3 以下代码使用JDK11编写。 1、体验Stream流 (1)案例需求 按照下面的要求完成…

SolidUI Gitee GVP

感谢Gitee,我是一个典型“吃软不吃硬”的人。奖励可以促使我进步,而批评往往不会得到我的重视。 我对开源有自己独特的视角,我只参与那些在我看来高于自身认知水平的项目。 这么多年来,我就像走台阶一样,一步一步参与…

Elasticsearch:带有自查询检索器的聊天机器人示例

本工作簿演示了 Elasticsearch 的自查询检索器 (self-query retriever) 将问题转换为结构化查询并将结构化查询应用于 Elasticsearch 索引的示例。 在开始之前,我们首先使用 langchain 将文档分割成块,然后使用 ElasticsearchStore.from_documents 创建…

【微服务】springcloud集成skywalking实现全链路追踪

目录 一、前言 二、环境准备 2.1 软件环境 2.2 微服务模块 2.3 环境搭建 2.3.1 下载安装包 2.3.2 解压并启动服务 2.3.3 访问web界面 三、搭建springcloud微服务 3.1 顶层公共依赖 3.2 用户服务模块 3.2.1 准备测试使用数据库 3.2.2 添加依赖 3.2.3 添加配置文件 …

如何保证本地缓存的一致性(和分布式缓存)

保证本地缓存和分布式缓存的一致性是一个关键的问题,因为这可以确保系统的健壮性和响应速度。以下是一些在Java中实现这一目标的方法: 1.使用一致性哈希:一致性哈希是一种特殊的哈希技术,它能够在节点增减时最小化哈希环上的数据分…

c++基础(对c的扩展)

文章目录 命令空间引用基本本质引用作为参数引用的使用场景 内联函数引出基本概念 函数补充默认参数函数重载c中函数重载定义条件函数重载的原理 命令空间 定义 namespace是单独的作用域 两者不会相互干涉 namespace 名字 { //变量 函数 等等 }eg namespace nameA {int num;v…

啊哈c语言——逻辑挑战9:水仙花数

有一种三位数特别奇怪,这种数的“个位数的立方”加上“十位数的 立方”再加上“百位数的立方”恰好等于这个数。例如: 153111555333,我们为这种特殊的三位数起了一个很好听的名字——“水仙花数”,那么请你找出所有的“水仙花数”…

Vue2 - Vue.observable 介绍

目录 1,介绍2,使用场景和 Vue 实例的区别 1,介绍 官网参考 可以让一个对象变成响应式数据。在 Vue 内部就是用它来处理传递给 Vue 的 data 对象,或是在单文件组件中 data() 返回的对象。 var vm new Vue({data: {count: 0} })…

MySQL学习笔记2: MySQL的前置知识

目录 1. MySQL是什么?2. 什么是客户端,什么是服务器?3. 服务器的特点4. 安装mysql5. mysql 客户端6. mysql 服务器7. mysql的本体8. MySQL 使用什么来存储数据?9. 数据库的多种含义10. MySQL 存储数据的组织方式 1. MySQL是什么? MySQL 是…

【Unity】 HTFramework框架(四十七)编辑器日志中使用超链接的技巧

更新日期:2024年1月3日。 Github源码:[点我获取源码] Gitee源码:[点我获取源码] 索引 日志中使用超链接超链接-网络地址超链接-本地地址超链接-项目资源文件超链接-脚本对象 日志中使用超链接 在编辑器控制台Console中的日志是支持富文本的&…

K8S集群部署解决工作节点couldn‘t get current server API group list问题

最近在自己电脑上装了VMWare Player,在上面装了两个Ubuntu虚拟机,为了方便学习云原生技术,决定在上面装一个2个节点(一个控制面,一个工作节点)的K8S集群。 参考这篇文章: Ubuntu 22.04 搭建K8…

Linux驱动学习—中断

1、中断基础概念 1.1 什么是中断 CPU在正常运行期间&#xff0c;由外部或者内部引起的时间&#xff0c;让CPU停下当前正在运行的程序&#xff0c;转而去执行触发他的中断所对应的程序&#xff0c;这就是中断。 响应中断的过程&#xff1a; <1>中断请求 <2>中断…

探索网络连接的netstat

文章目录 探索网络连接的netstat基本概述更多信息 探索网络连接的netstat 在Linux系统中&#xff0c;网络是至关重要的部分&#xff0c;而netstat命令是管理和监视网络连接的强大工具之一。 它提供了关于网络接口和路由表的详细信息&#xff0c;有助于了解网络连接状态、统计…

全国计算机等级考试| 二级Python | 真题及解析(10)

一、选择题 1.要实现将实数型变量a的值保留三位小数,以下python可以实现的是( ) A.a%0.001 B.a//0.001 C.round(a,3) D.round(3,a) 2.在Python中要交换变量a和b中的值,应使用的语句组是( )。 A…

通信原理期末复习——基础小题汇总(二)

个人名片&#xff1a; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的在校大学生 &#x1f42f;个人主页&#xff1a;妄北y &#x1f427;个人QQ&#xff1a;2061314755 &#x1f43b;个人邮箱&#xff1a;2061314755qq.com &#x1f989;个人WeChat&#xff1a;V…

【Docker】容器的相关命令

上一篇&#xff1a;创建&#xff0c;查看&#xff0c;进入容器 https://blog.csdn.net/m0_67930426/article/details/135430093?spm1001.2014.3001.5502 目录 1. 关闭容器 2.启动容器 3.删除容器 4.查看容器的信息 查看容器 1. 关闭容器 从图上来看&#xff0c;容器 aa…

【leetcode】力扣算法之有效的数独【中等难度】

题目描述 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08;请参考示例图&…