【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证明(面试常问到)

文章目录

  • 前言
  • 环形链表
  • 环形链表 II
  • 写在最后

前言

  • 本章的OJ练习相对于OJ练习(4)较为简单。不过,本章的OJ最重要的是要我们证明为何可以这么做。这也是面试中常出现的。

  • 对于OJ练习(4)-> 传送门 <-,分割链表以一种类似于归并的思想解得,回文链表以一种巧妙复用前面OJ题的思想解得。

  • 啰嗦一下:对于本章,最重要的是需要证明为什么这样做可以,所以我们不光要做出来OJ,还要能够理解并自行给出证明。


环形链表

  • 题目链接: -> 传送门 <-

  • 题目描述:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中存在环 ,则返回 true 。 否则,返回 false

带环链表类似于下面这种结构:

  • 是否有环,实际上就是链表的最后一个节点是否指向了链表其中的一个节点,如果有环,我们遍历一遍链表的话,会陷入死循环。那么我们该如何判断链表是否有环呢?

解题思路:

  • 由于带环链表直接遍历会陷入死循环,也就是说会无限在环内遍历下去,因此,这里可以引出一个追击问题:用快慢指针遍历链表。

  • 我们定义两个指针,分别是慢指针slow,快指针fast,这两个指针同时遍历链表,slow每次走一步,fast每次走两步。fast会先进入环然后在环内跑圈,当slow进入环后,这就是一个典型的追及问题了,slow每次在环内走一步,fast每次在环内走两步,两个指针的距离每次缩小1,最终fast会追上slowslow指向同一节点。当两个指针相等时,就可以判断该链表带环,因此判断条件就是fast == slow (return true)

  • 如果链表不带环,fast最终会指向NULL的前一个结点或者就指向NULL。因此,整个判断过程就结束了。

在这里插入图片描述

在这里插入图片描述

  • 可以看到,如果链表没有环,链表的结点个数为偶数时,fast是指向NULL结束,链表的节点个数为奇数时,fast是指向最后一个结点结束。

解题代码:

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head, * slow = head;

    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow) return true;
    }

    return false;
}

为什么快慢指针可以?

  • 快指针每次走两步,慢指针每次走一步,当两个指针都在环内的时候,就成了一个追击问题,两个指针的距离每次缩小一,最终快指针会追上慢指针,因此判断其有环。

  • 那假如快指针每次走三步,慢指针走一步呢?

我们将带环链表抽象成下图:

在这里插入图片描述
假设每次快指针走三步,慢指针每次走一步,当两个指针都进环后,此时的相对位置为:

在这里插入图片描述
我们记此时慢指针slow与快指针fast的距离为N,慢指针每次走一步,快指针每次走三步,因此N每次减少2,于是就有:

N - 2
N - 4
N - 6
N - 8
.....
最终有两种情况:
😃. N = 1,然后再减2 -> -1
😉. N = 2,然后再减2 -> 0

  • 如果N最后减为-1,那么再次追击,如果N最后减为0,则快指针等于慢指针,判断为true。所以得出:N为奇数时,追不上;当N为偶数时,一定追得上。

  • 如果追不上,最后fast会在slow的下一个位置,然后继续追击,那么,继续追击又是否追的上呢?

我们假设环的长度为C,那么此时再次追击两个指针的距离就为:C - 1,令T = C - 1,则:

T - 2
T - 4
T - 6
T - 8
.....
最终有两种情况:
😃. T = 1,然后再减2 -> -1
😉. T = 2,然后再减2 -> 0

  • 因此,这里又有两种情况,有了前面的推导,这里不难得出,当C为偶数时,则C - 1(T)为奇数,此时继续追不上,并且下一次也是一样,所以这里会陷入死循环;当C为奇数时,则C - 1为偶数,此时是追的上的。因此,C为偶数时,永远追不上,当C为奇数时,追的上。

所以,通过以上分析,快指针每次走三步,慢指针每次走一步不一定能判断是否为带环链表,可能会陷入死循环,尽管陷入死循环就说明带环。

那么快指针每次走4步,走5步,走n步呢?这里就不是我们该探讨的范围了,相信大家心里已经有答案了。


环形链表 II

  • 题目链接:-> 传送门 <-

  • 题目描述:给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。注意:不允许修改链表。

  • 与上一题不同的是,这一题首先是要判断链表是否带环,然后在带环的基础上返回链表入环的第一个节点。类似于下图:

在这里插入图片描述

解题思路:

  • 这里直接说做法:先以第一题的思路使用快慢指针找到快指针和慢指针相遇的那个点,然后一个指针从该点开始走,一个指针从头开始走,每次走一步,最终两个指针会在入环的第一个节点相遇,然后返回这个节点。

解题代码:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow = head, *fast = head;

    while (fast && fast->next)
    {
    	// 快指针每次走两步
        fast = fast->next->next;
        // 慢指针每次走一步
        slow = slow->next;

		// 如果找到相遇的那个点,就开始找入环的第一个节点
        if (slow == fast)
        {
            struct ListNode *cur = slow;
            // 一个从头开始走,一个从当前节点开始走
            while (cur != head)
            {
                head = head->next;
                cur = cur->next;
            }
            // 最终相遇的那个点就是入环的第一个节点
            return cur;
        }
    }
	
	// 如果链表不带环,就返回NULL
    return NULL;
}

证明:为什么一个指针从快慢指针相遇的那个点开始走,一个指针从头开始走,最终两个指针会在入环的第一个节点处相遇?

  • 假设快慢指针在pos位置相遇,设链表头到入环的第一个节点的距离为X, 入环的第一个节点到pos的距离为Ypos到入环的第一个节点的距离为L,整个环的周长为C

在这里插入图片描述

由此,我们计算一下,当快慢指针在pos相遇时分别走了多长的距离:

😃 快指针:X + nC + Y;
😉 慢指针:X + Y;

😮 为什么快指针有个nC而不是C
😮 为什么慢指针没有C?

  • 快指针有个nC是因为:有可能这个环的长度比较短,在慢指针入环时,快指针已经在环内走了n圈了。
  • 慢指针没有C是因为:慢指针入环后最多只会走C - 1步,不可能出现在环内步数超过一圈的情况,因此慢指针没有C

因此由快指针每次走两步,慢指针每次走一步的特点可以得出下面这个公式:

X + nC + Y = 2(X + Y);

化简得:

X = nC - Y;

进一步化简得:

X = (n - 1)C + (C - Y);

最终得:

X = (n - 1)C + L;

在这里插入图片描述

由此公式,当一个指针从pos开始走,他走了(n - 1)C,最终还是会在pos位置。而当(n - 1)C走完后,从头开始走的指针与入环的第一个节点的距离为L,与此时pos到入环的第一个节点的距离相等。因此,为什么这样的做法可以,以上就是答案。


写在最后

对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。

感谢阅读本小白的博客,错误的地方请严厉指出噢!

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

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

相关文章

ChatGPT-4 终于来了(文末附免费体验地址)

大家好&#xff0c;我是小钱学长。 ChatGPT4.0 重磅来袭&#xff0c;今天一打开plus页面出现的就是这个GPT-4的体验界面&#xff01;现在就带大家一起看看GPT4.0​。 进入之后是这样的 看到最下面有一行话&#xff0c;目前应该是4个小时限制100条消息。 GPT-4有什么优势&…

手把手学会DFS (递归入门)

目录 算法介绍 递归实现指数型枚举 递归实现排列型枚举 递归实现组合型枚举 算法介绍 &#x1f9e9;DFS 即 Depth First Search &#xff0c;中文又叫深度优先搜索&#xff0c;是一种沿着树的深度对其进行遍历&#xff0c;直到尽头之后再进行回溯&#xff0c;再走其他路线的…

springboot复习(黑马)

学习目标基于SpringBoot框架的程序开发步骤熟练使用SpringBoot配置信息修改服务器配置基于SpringBoot的完成SSM整合项目开发一、SpringBoot简介1. 入门案例问题导入SpringMVC的HelloWord程序大家还记得吗&#xff1f;SpringBoot是由Pivotal团队提供的全新框架&#xff0c;其设计…

GPT-4技术报告

摘要 链接&#xff1a;https://cdn.openai.com/papers/gpt-4.pdf 我们汇报了GPT-4的发展&#xff0c;这是一个大规模的多模态模型&#xff0c;可以接受图像和文本输入并产生文本输出。虽然在许多现实场景中&#xff0c;GPT-4的能力不如人类&#xff0c;但它在各种专业和学术基…

数智链接,新一代校园招聘解决方案

疫情3年市场巨变&#xff0c;00后新生代初登上求职舞台&#xff0c;中和作用下&#xff0c;牛客发现新生代求职发生明显变化&#xff0c;企业校招也要随之而变&#xff0c;并率先提出以种草、精准、专业为特点的新一代校园招聘解决方案。01.学生求职变了&#xff01;安全感、非…

奇异值分解(SVD)原理与在降维中的应用

奇异值分解(SVD)原理与在降维中的应用 奇异值分解(Singular Value Decomposition&#xff0c;以下简称SVD)是在机器学习领域广泛应用的算法&#xff0c;它不光可以用于降维算法中的特征分解&#xff0c;还可以用于推荐系统&#xff0c;以及自然语言处理等领域。是很多机器学习算…

GPT-4来袭:开启人工智能新时代

文章目录介绍GPT4 模型演示示例示例 1示例 2示例 3示例 4示例 5最后Reference介绍 2023年3月15日&#xff0c;OpenAI公司正式发布了先进的自然语言处理模型GPT-4&#xff0c;前不久发布的GPT-3.5模型只能理解文字的语言模型&#xff0c;而新发布的GPT4则是多模态模型&#xff…

【java】了解常见集合类

了解常见集合类 一、集合类框架 1、集合类框架结构图 首先我们要对集合类结构有一个大体的认识&#xff0c;所有集合都继承于迭代器&#xff0c;分为单列集合和映射集合&#xff0c;单列集合分为有序可重复和有序不可重复&#xff0c;大概结构如下图所示 2、主要集合类的介…

你真的知道如何系统高效地学习数据结构与算法吗?

文章目录前言&#xff1a;什么是数据结构&#xff1f;什么是算法&#xff1f;学习这个算法需要什么基础&#xff1f;学习的重点在什么地方&#xff1f;一些可以让你事半功倍的学习技巧1.边学边练&#xff0c;适度刷题2.多问、多思考、多互动3.打怪升级学习法4.知识需要沉淀&…

文心一言---中国版的“ChatGPT”狂飙的机会或许要出现了

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的在读研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三…

linux 基础

1.Shell 命令的格式如下&#xff1a;command -options [argument]command: Shell 命令名称。options&#xff1a; 选项&#xff0c;同一种命令可能有不同的选项&#xff0c;不同的选项其实现的功能不同。argument&#xff1a; Shell 命令是可以带参数的&#xff0c;也可以不带参…

【计算机二级Python】综合题目

计算机二级python真题 文章目录计算机二级python真题一、简单应用——明星投票二、综合应用题《评奖学金 两问》一、简单应用——明星投票 描述使用字典和列表型变量完成最有人气的明星的投票数据分析。投票信息由附件里的文件vote.txt给出,一行只有一个明星姓名的投票才是有效…

【BLE 5.3无线MCU CH582】1、初识CH582开发板(开箱)

1、认识板子 优点&#xff1a; &#xff08;1&#xff09;引脚全部引出&#xff1b; &#xff08;2&#xff09;USB下载程序&#xff1b; &#xff08;3&#xff09;TYPE-C接口好评&#xff1b; &#xff08;4&#xff09;板载连个两个USB口&#xff0c;都可以供电&#xff1b;…

前端性能优化之HTTP缓存

前端缓存 前端缓存可分为两大类&#xff1a;HTTP 缓存和浏览器缓存。 我们今天重点是 HTTP 缓存&#xff0c;下面这张图是前端缓存的一个大致知识点&#xff1a; HTTP 缓存 首先解决困扰绕人们的老大难问题&#xff1a; 一、什么是HTTP缓存&#xff1f; HTTP 缓存会存储与请…

六个实用技巧让你轻松写出优雅的链表代码

文章目录&#x1f4d5;前言&#xff1a;如何轻松写出正确的链表代码&#xff1f;&#x1f4d6;技巧一&#xff1a;理解指针或引用的含义&#x1f4d6;技巧二&#xff1a;警惕指针丢失和内存泄漏&#x1f4d6;技巧三&#xff1a;利用哨兵简化实现难度&#x1f4d6;技巧四&#x…

HTTP 协议

文章目录1. 前言2. HTTP 协议3. fiddler 的安装与认识4. HTTP 协议报文格式4.1 请求4.2 响应5. 构造 HTTP 请求5.1 基于 form 表单构造 HTTP 请求5.2 基于 ajax 构造 HTTP 请求6. postman7. HTTPS7.1 加密7.2 HTTPS 的工作过程1. 前言 前面几篇文章 &#xff0c; 说了关于 前端…

C++继承[万字详解]

目录 一.继承的介绍 1.1、继承的概念 1.2、继承的定义 1.2.1、定义格式 1.2.2、继承关系和访问限定符 1.2.3、继承基类成员后&#xff0c;在子类中成员访问方式的变化 二.基类和派生类对象赋值转化 三.继承中的作用域 四.派生类的默认成员函数 ★派生类的构造函数 派…

有关pytorch的一些总结

Tensor 含义 张量&#xff08;Tensor&#xff09;&#xff1a;是一个多维数组&#xff0c;它是标量、向量、矩阵的高维拓展。 创建 非随机创建 1.用数组创建 将数组转化为tensor np.ones([a,b]) 全为1 #首先导入PyTorch import torch#数组创建 import numpy as np anp.arr…

4.类的基本概念

目录 4.1 类的概述 类是一种活动的数据结构 4.2 程序和类&#xff1a;一个快速实例 4.3 声明类 ​4.4 类成员 4.4.1 字段 1.显示和隐式字段初始化 2. 声明多个字段 4.4.2 方法 4.5 创建变量和类的实例 4.6 为数据分配内存 合并这两个步骤 4.7 实例成员 4.8 访问修饰…

2023年天津市逆向re3.exe解析(超详细)

2023年天津市逆向re3.exe解析 1.拖进IDA里进行分析2.动态调试(过程省略了)3.解密加密算法4.输入FLAG 回显成功!1.拖进IDA里进行分析 打开后是这么一个程序,直接找到main函数f5反编译即可,这里要注意程序第一次反编译出的代码会有点问题,需要点进引用的那些其他sub函数里面…
最新文章