单链表OJ题(课堂总结)

1.链表的带环问题

       

上图就是一个典型的带环链表

   1.1如何判读链表是否带环? 

   最常见的方法就是利用快慢指针,快指针追加慢指针,当二者相等的时候即可判断链表带环

其实现的代码如下:

bool hasCycle(struct ListNode*head)

{
     struct ListNode* slow = head,*fast = head;

     while(fast && fast->next)

    {

            slow = slow->next;

            fast = fast ->next->next;

            if(slow == fast)

                return true;

    }

           return false;

}

 1.2 为什么快慢指针一定会相遇 

      1.2.1 两指针每走一步其距离缩小1

    假设slow进环的时候fast与其的距离为N,此时每当slow走一步,fast与slow的距离都会缩小1,最后缩小到0,从而两指针相遇。

      1.2.2 两指针每走一步其距离缩小2

初步证明:

  1.N是偶数,第一轮就追上。
       2.N是奇数,第一轮就会错过,距离变成C-1(C为环的长度)。
           a.如果C-1是偶数,下一轮就追上了
           b.如果C-1是奇数,那么就永远追不上

深度证明:

     假设slow进环时,fast跟slow的距离为N

     slow走的距离是:L

     fast走的距离:L+x*C+C-N

     slow进环时,假设fast已经在环里转了x圈

     如果fast走的距离是slow的3倍

     3*L = L+x*C + C-N

     2*L = (x+1)*C-N

    偶数 = (x+1)*偶数-奇数      所以只有两种情况:  N是奇数,C也是奇数

                                                                                   N是偶数时,C也是偶数

    由此可以得出N是奇数且C是偶数不能同时存在,在初步证明中的永远追不上不成立

  把两种情况代入初步证明中可以得出结论

    结论:一定能追上

         N偶数第一轮就追上了

         N是奇数第一轮追不上,C-1是偶数第二轮就追上

 1.3 找环的入口点

    1.3.1 方法一       

一个指针从头结点开始前进,而slow指针在与fast相遇点开始前进,当head指针和slow指针相遇的时候,该点为环的入口点。

证明如下: 

相遇时:

slow走的路程:L + N

fast走的路程:L+x*C+N

fast走的路程是slow的2倍:化简后的公式为:L =x*C-N ->  L = (x-1)*C + C - N

以下为代码的实现:

struct ListNode*meet = slow;

while(meet != head)

{

     meet = meet ->next;

     head = head ->next;

}

      return meet;

1.3.2 方法二 

 

 newhead = meet->next;

  newhead =NULL;

通过上述两个操作,让找环入口点转化为找两个链表的交点问题

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

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

相关文章

【爬虫软件】2024最新短视频评论区抓取工具

一、背景说明 1.0 采集目标 采集DOU音评论数据对引流截流和获客有很多好处。首先,通过分析DOU音评论数据,我们可以更好地了解用户对于产品或内容的喜好和需求,从而调整营销策略,吸引更多用户关注和点击。其次,评论数据…

小而美的前端库推荐

小而美,指的是“小即是美”的事物,这是马云在 2009年 APEC 中小企业峰会上首次提出的观点 👍 前端有很多小而美的库,接入成本很低又能满足日常开发需求 🎉

StringMVC

目录 一,MVC定义 二,SpringMVC的基本使用 2.1建立连接 - RequestMapping("/...") ​编辑 2.2请求 1.传递单个参数 2.传递多个参数 3.传递对象 4.参数重命名 5.传递数组 6. 传递集合 7.传递JSON数据 8. 获取url中数据 9. 传递文…

深度学习中的多GPU训练(Pytorch 20)

一 多GPU训练 下面详细介绍如何从零开始并行地训练网络,这里需要运用小批量随机梯度下降算法。后面我还讲介绍如何使用高级API并行训练网络。 我们从一个简单的计算机视觉问题和一个稍稍过时的网络开始。这个网络有多个卷积层和汇聚层,最后可能 有几个…

Android:将时间戳转换为本地时间格式

一、效果图 图1,中国的时间格式 图2,美国的时间格式 二、StringUtil.kt代码 import java.text.DateFormat import java.text.SimpleDateFormat import java.util.* object StringUtil {fun formatTimestamp(currentTime: Long): String {var sdf Si…

dolphinscheduler standalone安装

官方文档:https://dolphinscheduler.apache.org/en-us/docs/3.1.3/guide/installation/standalone 1.安装(以放在/home为例) 下载见:https://download.csdn.net/download/taotao_guiwang/89311365 tar -xvzf apache-dolphinsche…

美团Java社招面试题真题,最新面试题

如何处理Java中的内存泄露? 1、识别泄露: 使用内存分析工具(如Eclipse Memory Analyzer Tool、VisualVM)来识别内存泄露的源头。 2、代码审查: 定期进行代码审查,关注静态集合类属性和监听器注册等常见内…

C++ 数据结构算法 学习笔记(33) -查找算法及企业级应用

C 数据结构算法 学习笔记(33) -查找算法及企业级应用 数组和索引 日常生活中,我们经常会在电话号码簿中查阅“某人”的电话号码,按姓查询或者按字母排 序查询;在字典中查阅“某个词”的读音和含义等等。在这里,“电话号码簿”和…

nginx文件解析漏洞测试

环境条件:ubuntu14,已安装docker,docker pull ubuntu:14.04.5 一、Nginx配置 1、使用docker启动容器: docker run -itd --name ubuntu -p 8088:80 ubuntu:14.04.5 2、进入容器: docker exec -it ubuntu /bin/bash 3、然后使用以下语句安装相关环境…

(四)手把手教你内网穿透,实现外网主机访问内网服务器

背景:书接上回, 服务器的使用-CSDN博客 课题组成员都有自己的账号,且能通过内网访问服务器,进行远程连接了。我们知道内网中的主机可以访问公网的主机,反之不可以访问。那么如果课题组成员在家不在内网区域内&#x…

ai发展会不会带来企业的员工垄断呢

写代码写累了,写点个人不成熟的想法,作为记录 随着gpt-4o发布,可以预计的是,AI逐渐能够通过各种外接设备和传感器和真实世界实时交互。那么未来一个接上摄像头,键盘,音响,可移动身体的的AI还会…

如何注册Claude3?解决Claude3无海外手机号接收验证码的问题以及如何订阅Claude Pro

原文链接:如何注册 Claude3?解决 Claude3 无海外手机号接收验证码的问题以及如何订阅 Claude Pro 前言 Claude3已经出来有一段时间了,大家有没有体验过呢?不过从目前来看,Anthropic公司总共推出了3个模型&#xff1…

Jenkins安装 :AWS EC2 Linux

1 JDK11 install # 用的yum安装 # 压缩包安装,下载的jdk-11.0.22_linux-x64_bin.tar.gz在EC2解压,配置环境变量,运行jenkins的时候会报错$ yum -y list java-11* Available Packages java-11-amazon-corretto-devel.x86_64 …

用队列实现栈 用栈实现队列 设计循环队列

用队列实现栈 思路 栈的特点:后进先出 队列的特点:先进先出 使用两个队列实现栈: 我们可以使用两个队列,一个队列为:空队列,一个队列为:非空队列 当我们要出队列时: 将 size - …

多态

多态的概念 通俗来说,就是多种形态,具体点就是完成某个行为,当不同的对象去完成时会产生出不同的状态 多态的定义及实现 多态构成的条件 1、必须通过基类的指针或者引用调用虚函数 2、子类必须对基类的虚函数进行重写 虚函数 被关键字vi…

内网横向移动小补充 --->PTK

大家别急,我的基于资源的约束性委派攻击还在写,这个东西一时半会讲不清楚,所以我在这里先来补充一点横向移动以前没说好的东西!!! 在更啦,别催啦~~~~ 还记得我之前在内网渗透里面讲过这个PTK&a…

2024.5.22 关于 SpringCloud —— Nacos 配置管理

目录 Nacos 配置统一管理 Nacos 配置热部署 Nacos 多环境配置共享 配置优先级 Nacos 配置统一管理 实例理解 我们想要利用 Nacos 在 user-service 的 application.yml 配置文件中新增配置项此处我们将新增配置日期格式为 yyyy-MM-dd HH:mm:ss下图为新增 Nacos 配置统一管理…

基于STM32实现智能园艺系统

目录 引言环境准备智能园艺系统基础代码示例:实现智能园艺系统 土壤湿度传感器数据读取水泵控制温湿度传感器数据读取显示系统用户输入和设置应用场景:智能农业与家庭园艺问题解决方案与优化收尾与总结 1. 引言 本教程将详细介绍如何在STM32嵌入式系统…

基于Zynq 7000 SoC的迁移设计

基于Zynq 7000 SoC的迁移设计 Vivado IDE工具使用IP集成器进行嵌入式开发。各种IP Vivado IDE IP目录中提供,以适应复杂的设计。您也可以添加 自定义IP到IP目录。 您可以将基于Zynq 7000平台处理器的设计迁移到Vivado design Suite中 使用以下步骤。 1.生成系统基础…

【搜索方法推荐】高效信息检索方法和实用网站推荐

博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G算力网络技术标准研究。 博客…