链表带环问题(详解)

在这里插入图片描述

🔆链表带环问题(详解)

  • 🔆I 给定一个链表,判断链表中是否有环。
  • 🔆II 给定一个链表,返回链表开始入环的第一个结点。 如果链表无环,则返回 NULL。
  • 🔆复制带随机指针的链表
  • 🔆结语

🔆I 给定一个链表,判断链表中是否有环。

OJ链接

解题思路:
快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表其实位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。
思路解释:

  • 假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在满指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。
    在这里插入图片描述

答案:

bool hasCycle(struct ListNode *head) {
    if(head == NULL || head->next == NULL)
        return false;
    struct ListNode* slow = head;
    struct ListNode* fast = head->next->next;
    while(slow != fast)
    {
        if(fast == NULL || fast->next == NULL)
            return false;
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

🔆II 给定一个链表,返回链表开始入环的第一个结点。 如果链表无环,则返回 NULL。

OJ链接

  • 结论
    让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇
  • 证明
    在这里插入图片描述

答案:

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL) {
        slow = slow->next;
        if (fast->next == NULL) {
            return NULL;
        }
        fast = fast->next->next;
        if (fast == slow) {
            struct ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return NULL;
}

🔆复制带随机指针的链表

OJ链接

链表实例:
在这里插入图片描述

1.根据遍历到的原节点创建对应的新节点,每个新创建的节点是在原节点后面。
在这里插入图片描述
2.设置新链表的随机指针,第一个新节点的随机指针=第一个旧节点随机指针指向节点的下一个节点,依次类推。
在这里插入图片描述
3.解开旧链表与新链表的链接,恢复旧链表,链接新链表。
在这里插入图片描述

答案:

 struct Node* BuyNode(int x) {
     struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
     if (newnode == NULL){
         exit(-1);
     }
     newnode->val = x;
     newnode->next = NULL;
     return newnode;
 }

struct Node* copyRandomList(struct Node* head) {
	if (head == NULL) {
        return NULL;
    }

    //1、申请新节点,链接到每个旧节点的后面
    struct Node* cur = head, *next = NULL;
    while (cur) {
        struct Node* newnode = BuyNode(cur->val);
        next = cur->next;
        cur->next = newnode;
        newnode->next = next;
        cur = next;
    }

    //2、拷贝原链表的random指针,相对于新链表的相对位置
    cur = head;
    while (cur) {
        next = cur->next;
        if (cur->random == NULL) {
            next->random = NULL;
        }else {
            next->random = cur->random->next;
        }
        cur = next->next;
    }

    //3、解开新链表与旧链表的链接,恢复旧链表和新链表的链接
    cur = head;
    struct Node* newHead = cur->next;
    while (cur) {
        next = cur->next;
        cur->next = next->next;
        if (cur->next == NULL) {
            next->next = NULL;
        }else {
            next->next = cur->next->next;
        }
        cur = cur->next;
    }
    return newHead;
}

🔆结语

到这里这篇博客已经结束啦。
这份博客👍如果对你有帮助,给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️,谢谢!!!
如果有什么疑问或不同的见解,欢迎评论区留言欧👀

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

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

相关文章

集成方法!

目录 关注降低variance,选择bias较小的基学习器 Bagging Stacking Random Forest 关注降低bias,选择variance较小的基学习器 Adaboost Boosting 关注降低variance,选择bias较小的基学习器 Bagging 给定m个样本的数据集,利用有放回的随机采样法,得…

【Linux】操作系统(Operator System)

操作系统(Operator System )一、操作系统的概念二、操作系统的作用三、系统调用和库函数一、操作系统的概念 操作系统是一组控制和管理计算机软硬件资源,为用户提供便捷使用的计算机程序的集合,是配置在计算机硬件系统上的第一层…

模拟实现字符串有关函数(详细讲解)

在编写程序时,我们都喜欢写出简便并且效率高的代码,那么此时库函数中的有些函数就是我们的不二之选,那么,大家汇米你实现吗?下面就先从我们最简单的字符串函数说起: 1.strlen 这个是函数的格式&#xff0c…

做了个springboot接口参数解密的工具,我给它命名为万能钥匙(已上传maven中央仓库,附详细使用说明)

前言:之前工作中做过两个功能,就是之前写的这两篇博客,最近几天有个想法,给它做成一个springboot的start启动器,直接引入依赖,写好配置就能用了 springboot使用自定义注解实现接口参数解密,普通…

SpringSecurity学习(七)授权

授权 什么是权限管理 权限管理核心概念 SpringSecurity权限管理策略 基于URL地址的权限管理 基于方法的权限管理 一、权限管理 二、授权核心概念 在认证的过程成功之后会将当前用户登录信息保存到Authentication对象中,Authentication对象中有一个getAuthorities…

ChatGPT-4震撼发布

3月15日消息,美国当地时间周二,人工智能研究公司OpenAI发布了其下一代大型语言模型GPT-4,这是其支持ChatGPT和新必应等应用程序的最新AI大型语言模型。该公司表示,该模型在许多专业测试中的表现超出了“人类水平”。GPT-4, 相较于…

基于Java+Springboot+vue高校资源共享交流平台设计和实现

博主介绍:✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专…

SpringBoot介绍。

目录 一、SpringBoot简介 1、SpringBoot开发步骤 2、官网构建工程 3、SpringBoot概述 二、配置文件 1、配置文件格式 2、yaml格式 3、yaml配置文件数据读取 三、多环境配置 1、yam文件 2、properties文件 3、命令行启动参数设置 四、SpringBoot整合 1、SpringBo…

界面开发(4)--- PyQt5实现打开图像及视频播放功能

PyQt5创建打开图像及播放视频页面 上篇文章主要介绍了如何实现登录界面的账号密码注册及登录功能,还简单介绍了有关数据库的连接方法。这篇文章我们介绍一下如何在设计的页面中打开本地的图像,以及实现视频播放功能。 实现打开图像功能 为了便于记录实…

OCPC系列 - OCPC介绍扫盲贴来啦

本文对oCPC做个介绍,它是一种智能投放模式,系统通过对广告主转化数据的对接和深度理解,实时预估每一次点击的转化率并基于竞争环境智能出价,通过强化高转化率曝光机会的获取,弱化低转化率曝光机会的展现,以…

力扣-进店却未进行过交易的顾客

大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目:1581. 进店却未进行过交易的顾客二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行…

文心一言正式对标GPT-4,是青铜还是王者?

昨天,OpenAI正式发布GPT-4模型 号称史上最先进的AI系统 今天,百度文心一言在万众瞩目中闪亮登场 这款产品被视为中国版ChatGPT 在这一个多月内备受关注 文心一言某种程度上具有了对人类意图的理解能力 回答的准确性、逻辑性、流畅性都逐渐接近人类…

Go 微服务开发框架 DMicro 的设计思路

Go 微服务开发框架 DMicro 的设计思路 DMicro 源码地址: Gitee:dmicro: dmicro是一个高效、可扩展且简单易用的微服务框架。包含drpc,dserver等 背景 DMicro 诞生的背景,是因为我写了 10 来年的 PHP,想在公司内部推广 Go, 公司内部的组件及 rpc 协议都…

多模态特征融合:图像、语音、文本如何转为特征向量并进行分类

多模态特征融合前言输入层,数据集转为特征向量图像语音什么是时域信号,什么是频域信号语音信号转换 - 1.傅立叶变换语音信号转换 - 2.梅尔频率倒谱系数文本词袋模型词嵌入模型输出层,多模态模型合并前言 学习多模态的话题可以从深度学习的分…

【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.57】引入可形变卷积

文章目录前言一、解决问题二、基本原理三、​添加方法四、总结前言 作为当前先进的深度学习目标检测算法YOLOv8,已经集合了大量的trick,但是还是有提高和改进的空间,针对具体应用场景下的检测难点,可以不同的改进方法。此后的系列…

[JS与链表]普通链表

为什么要用链表要储存一系列数据,最常用的数据结构是数组。数组有个缺点就是在中间插入或删除元素需要移动元素,成本很高。什么是链表链表也是有序元素的集合结构。链表中的元素在内存中并不是连续放置的。每个元素都可以理解为一个对象。包含了本身元素…

简单了解JSP

JSP概念与原理概念: Java Server Pages,Java服务端页面一种动态的网页技术,其中既可以定义 HTML、JS、CSS等静态内容,还可以定义Java代码的动态内容JSP HTML Java, 用于简化开发JSP的本质上就是一个ServletJSP 在被访问时,由JSP容…

博途PLC开放式以太网通信TRCV_C指令应用编程(运动传感器UDP通信)

博途PLC开放式以太网通信TSENG_C指令应用,请参看下面的文章链接: 博途PLC 1200/1500PLC开放式以太网通信TSEND_C通信(UDP)_plc的udp通信_RXXW_Dor的博客-CSDN博客开放式TSEND_C通信支持TCP 、UDP等,关于TSEND_C的TCP通信可以参看下面这篇文章:博途PLC 1200/1500PLC开放式…

opencv识别车道线(霍夫线变换)

目录1、前言2、霍夫线变换2.1、霍夫线变换是什么?2.2、在opencv中的基本用法2.2.1、HoughLinesP函数定义2.2.2、用法3、识别车道3.1、优化3.1.1、降噪3.1.2、过滤方向3.1.3、截选区域3.2、测试其它图片3.2.1、代码3.2.2、图片13.2.3、图片23.2.4、图片31、前言 最近…

C++模拟实现红黑树

目录 介绍----什么是红黑树 甲鱼的臀部----规定 分析思考 绘图解析代码实现 节点部分 插入部分分步解析 ●父亲在祖父的左,叔叔在祖父的右: ●父亲在祖父的右,叔叔在祖父的左: 测试部分 整体代码 介绍----什么是红黑树 红…
最新文章