当前位置: 首页 > news >正文

【数据结构】链表相关题目(中档题)

在这里插入图片描述

🚀write in front🚀
📜所属专栏:初阶数据结构
🛰️博客主页:睿睿的博客主页
🛰️代码仓库:🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!!
关注我,关注我,关注我你们将会看到更多的优质内容!!

在这里插入图片描述

文章目录

  • 前言:
    • 例题1:
      • 方法1:
      • 方法2:
    • 例题2:
      • 完整代码:
  • 总结

前言:

  在前面的练习中,我们简单练习了链表的相关题目,今天我们在来做一些拓展!

例题1:

在这里插入图片描述在这里插入图片描述
在这里插入图片描述

方法1:

  在上一篇博客里面,我们讲述了快慢指针的概念:通过步长的差异处理环的问题。而这道题我们要寻找入口点,我们该如何处理呢?

首先,我们假设

  • 起始点到入口的长度为L,
  • 入口到相遇点的距离为X,
  • 环的长度为C。

接下来我们通过快慢指针的两个性质(快指针是慢指针步数的两倍,快慢指针最后相遇)列出一个方程:
在这里插入图片描述
  由得出的结论我们可以看出,如果让一个指针a从起点出发,另一个指针b从相遇点出发,如果是闭环,则他们一定会相遇!(这里我们并不需要算出n的值,因为n的值是是让a指针多走n-1个整圈,不影响和b指针相遇)。
下面我们来看看代码:

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

方法2:

  如果同学们在做题时无法自己推出这个结论,那么此时我们也可以将相遇点断开,此时就变成了寻找公共节点的题目了。
在这里插入图片描述

例题2:

在这里插入图片描述
对于这道题目,大家可能最先会想到计数器的方法,通过记录每个random的位置,在拷贝的链表里面找到对于位置依次连接。但是这样会导致时间复杂度非常的低下:O(N^2)
在这里插入图片描述
为了降低复杂度,就不得不使用另外一种方法。要降低时间复杂度,我们就希望能快速的找到原节点的拷贝节点。怎么找呢?

1.拷贝节点链接在原节点后面
在这里插入图片描述
在这里插入图片描述

2.此时拷贝节点的random就是原节点random->next
在这里插入图片描述
在这里插入图片描述

3.拷贝节点解下来,链接成新链表,最后将原链表还原。
在这里插入图片描述
在这里插入图片描述

完整代码:

struct Node* copyRandomList(struct Node* head) 
{//第一步struct Node*cur=head;while(cur){struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));struct Node* next=cur->next;cur->next=newnode;newnode->next=next;newnode->val=cur->val;cur=next;}//第二步cur=head;while(cur){struct Node*prev=cur->next;if(cur->random==NULL){prev->random=NULL;}else{prev->random=cur->random->next;}cur=cur->next->next;}//第三步struct Node* newhead=NULL,*newtail=NULL;cur=head;while(cur){struct Node*prev=cur->next;struct Node*next=prev->next;if(newhead==NULL){newhead=newtail=prev;}else{newtail->next=prev;newtail=prev;}cur=next;}return newhead;
}

总结

  链表的相关题目到这里就结束了,当然同学们也可以去oj看看其他题:oj题
  更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

专栏订阅:
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易,辛苦各位小伙伴们动动小手,👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要!最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!

在这里插入图片描述

相关文章:

【数据结构】链表相关题目(中档题)

🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对…...

小菜鸟Python历险记:(第四集)

今天写的文章是记录我从零开始学习Python的全过程。在Python中函数是非常重要的,这里也可以称为方法。在前面分享的几篇文章中用到的方法有print(),str(),int().这些都是方法,而除了上面写的这几种内置方法以外,我们也可以自己在程序中自定义…...

字符函数和字符串函数【下篇】

文章目录🎖️1.函数介绍📬1.8. strstr📬1.9. strtok📬1.10. strerror📬1.11. memcpy📬1.12. memmove📬1.13. memcmp📬1.14. memset🎖️1.函数介绍 📬1.8. st…...

【CSS】盒子模型内边距 ② ( 内边距复合写法 | 代码示例 )

文章目录一、内边距复合写法1、语法2、代码示例 - 设置 1 个值3、代码示例 - 设置 2 个值4、代码示例 - 设置 3 个值5、代码示例 - 设置 4 个值一、内边距复合写法 1、语法 盒子模型内边距 可以通过 padding-left 左内边距padding-right 右内边距padding-top 上内边距padding-…...

uni-app ——使用uploadFile上传多张图片

前言:最近的工作中出现了一个功能点,具体写法我在前面的文章中已经阐述过,不过之前的情况是上传图片调用后端的一个接口,整个表单页面提交的时候调用的是另一个接口,我也从中学到了另外的一种方法,写到这里…...

Linux - 进程控制(进程等待)

进程等待必要性之前讲过,子进程退出,父进程如果不管不顾,就可能造成‘僵尸进程’的问题,进而造成内存泄漏。另外,进程一旦变成僵尸状态,那就刀枪不入,“杀人不眨眼”的kill -9 也无能为力&#…...

Python 可视化最频繁使用的10大工具

今天介绍Python当中十大可视化工具,每一个都独具特色,惊艳一方。 文章目录Matplotlib技术提升SeabornPlotlyBokehAltairggplotHoloviewsPlotnineWordcloudNetworkxMatplotlib Matplotlib 是 Python 的一个绘图库,可以绘制出高质量的折线图、…...

Windows与Linux端口占用、查看的方法总结

Windows与Linux端口占用、查看的方法总结 文章目录Windows与Linux端口占用、查看的方法总结一、Windows1.1Windows查看所有的端口1.2查询指定的端口占用1.3查询PID对应的进程1.4查杀死/结束/终止进程二、Linux2.1lsof命令2.2netstat命令一、Windows 1.1Windows查看所有的端口 …...

48天强训 Day1 JavaOj

48天强训 & Day1 & JavaOj 1. 编程题1 - 组队竞赛 组队竞赛_牛客笔试题_牛客网 (nowcoder.com) 1.1 读题 1.2 算法思想基础 我们应该尽量的让每一个队伍的中间值都最大化~我们应该尽量的让每一个队伍的最小值都足够小~前33%的不应该都作为每个队伍的最大值~ 接下来…...

崩溃的一瞬间

——我可以忍受黑暗,除非我从未见过光明 原来,人真的会崩溃,如果不是昨夜的眼泪,我到现在还不知道人为什么会在一瞬间崩溃。 刚和认识不久的女孩子聊完天准备入睡。忽然想到自己可能过几个月就要离开这座待了仅一年多的城市…...

13回归网络:HTTP/2是怎样的网络协议?

本篇文章我们先放下实践,回归网络,深入gRPC底层的HTTP/2协议,去探究一下框架底层网络协议的原理,提升对高性能网络协议的认知,相信读完这篇文章以后,我们就可以了解HTTP/2有哪些优势,为什么gRPC要使用HTTP/2作为底层的传输协议。 在众多研究HTTP/2的博客和资料中,最具…...

CSS学习笔记——基础选择器,字体属性,文本属性,三种样式表

文章目录基础选择器标签选择器类选择器多类名使用方式id选择器通配符选择器字体属性字体系列字体字号字体粗细文字样式复合属性文本属性文本颜色对齐文本装饰文本文本缩进行间距CSS的三种样式表行内样式表(行内式)内部样式表(嵌入式&#xff…...

第十四届蓝桥杯三月真题刷题训练——第 16 天

目录 第 1 题:英文字母 问题描述 输入格式 输出格式 样例输入 1 样例输出 1 样例输入 2 样例输出 2 评测用例规模与约定 运行限制 代码: 第 2 题:单词分析 题目描述 输入描述 输出描述 输入输出样例 运行限制 数组代码&…...

鸟哥的Linux私房菜 Shell脚本

第十二章、学习 Shell Scripts https://linux.vbird.org/linux_basic/centos7/0340bashshell-scripts.php 12.2 简单的 shell script 练习 #!/bin/bash# Program: # User inputs his first name and last name. Program shows his full name.read -p "Please in…...

FPGA基于RIFFA实现PCIE采集ov5640图像传输,提供工程源码和QT上位机

目录1、前言2、RIFFA理论基础3、设计思路和架构4、vivado工程详解5、上板调试验证并演示6、福利:工程代码的获取1、前言 PCIE是目前速率很高的外部板卡与CPU通信的方案之一,广泛应用于电脑主板与外部板卡的通讯,PCIE协议极其复杂&#xff0c…...

week13周报

一.动态规划走楼梯2难点:不能连续走三次两级台阶如何表示思路:可以用二维数组f[i][j],i表示当前台阶数,j表示已经连续走了j次二级台阶了转移方程:f[i2][j1]f[i2][j1]f[i][j] 当j!2时,我们可以选择走二级台阶…...

离散选择模型中的分散系数theta到底该放在哪里呢?

前言 \quad~~一直都在想为啥子离散选择模型中分散系数以分母形式出现而在路径选择公式中以系数形式出现呢?看着公式想了想,现在想出了一个似乎感觉应该差不多很合理的答案,希望与大家一起探讨。 进入正题 根据随机效用理论,决策…...

【CSAPP】进程 | 上下文切换 | 用户视角下的并发进程

💭 写在前面:本文将学习《深入理解计算机系统》的第六章 - 关于异常控制流和系统级 I/O 的 进程部分。CSAPP 是计算机科学经典教材《Computer Systems: A Programmers Perspective》的缩写,该教材由Randal E. Bryant和David R. OHallaron 合著…...

节流还在用JS吗?CSS也可以实现哦

函数节流是一个我们在项目开发中常用的优化手段,可以有效避免函数过于频繁的执行。一般函数节流用在scroll页面滚动,鼠标移动等。 为什么需要节流呢,因为触发一次事件就会执行一次事件,这样就形成了大量操作dom,会出现卡顿的情况…...

带你看看 TypeScript 5.0 的新特性

一、写在前面 TypeScript 5.0 已经于 2023 年 3 月 16 日发布了,带来了许多新功能,同时也在性能方面进行了优化,下面让我们来一起看看新版 TypeScript 中比较有重要的变化吧。 二、新特性 2-1、速度、包体积优化 首先是新版本性能的提升&…...

CASS11.0再升级:新增实用功能与BUG修复全解析(2022.5.11版)

1. CASS11.0版本升级概览 作为测绘行业的老牌软件,CASS11.0这次更新又带来了不少惊喜。记得去年11月刚发布时,我就第一时间安装体验过,当时就被它的3D建模能力和土方计算优化惊艳到了。没想到短短半年时间,研发团队又连续推出了三…...

别再手动输路径了!用VS Code Remote-WSL一键直达Ubuntu 20.04的home目录

极速直达WSL开发环境:VS Code高效工作流全指南 每次在Windows和WSL之间来回切换路径,就像在两个平行宇宙间手动搭建桥梁。作为深度使用WSL的开发者,我经历过无数次在资源管理器地址栏手输\\wsl$的痛苦,也曾在终端反复cd到项目目录…...

Streamlit+像素风=高效零售AI?Ostrakon-VL部署完整指南

Streamlit像素风高效零售AI?Ostrakon-VL部署完整指南 1. 项目概览:当零售AI遇上像素艺术 想象一下,你正在玩一款90年代的复古游戏,但这次你不是在打怪升级,而是在用AI分析零售店铺的货架陈列。这就是Ostrakon-VL扫描…...

丹青幻境·Z-Image Atelier部署教程:Docker Compose一键启停方案

丹青幻境Z-Image Atelier部署教程:Docker Compose一键启停方案 1. 学习目标与前置准备 本教程将手把手教你如何使用Docker Compose快速部署丹青幻境Z-Image Atelier数字艺术创作平台。通过本教程,你将学会: 如何在5分钟内完成环境搭建如何…...

化整为零、分而治之、异步编排:一文读懂现代并发的底层心法

LongAdder:化整为零,热点分散 在Java多线程编程中,‌原子变量(如AtomicLong)‌通过CAS操作实现线程安全的累加。然而,在高并发场景下,大量线程争抢同一原子变量会引发严重的‌缓存一致性问题‌。…...

OpenClaw日志分析:千问3.5-35B-A3B-FP8任务执行问题定位

OpenClaw日志分析:千问3.5-35B-A3B-FP8任务执行问题定位 1. 问题背景与日志分析的价值 上周我在尝试用OpenClaw自动化处理一批技术文档时,遇到了任务频繁中断的问题。当时对接的是千问3.5-35B-A3B-FP8模型,系统提示"模型响应异常"…...

如何轻松获取网页媒体资源?猫抓开源工具让资源提取效率提升3倍

如何轻松获取网页媒体资源?猫抓开源工具让资源提取效率提升3倍 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 你是否曾在浏览网页时遇…...

Mojo调用PyTorch模型推理却遭遇内存泄漏?——国家级实验室验证的4层内存隔离架构首次公开

第一章:Mojo调用PyTorch模型推理却遭遇内存泄漏?——国家级实验室验证的4层内存隔离架构首次公开在高性能AI边缘部署场景中,Mojo语言通过其零开销FFI机制调用PyTorch C前端(LibTorch)实现低延迟推理,但实测…...

电散热器为何能适配多场景采暖?

一、设备概述:3kW 220V电散热器的核心定位3kW 220V电散热器是一款功率适中、电压适配家用及小型商用场景的便捷采暖设备,凭借无需复杂管道铺设、即开即热的优势,成为现代采暖的热门选择。其额定功率3kW、额定电压220V,适配家庭、办…...

自动驾驶开发必备:Vscode+Git双神器组合的隐藏技巧(含分支管理秘籍)

自动驾驶开发必备:VscodeGit双神器组合的隐藏技巧(含分支管理秘籍) 在自动驾驶开发领域,高效的代码管理和协作流程是项目成功的关键因素。随着代码库规模不断扩大,团队规模持续增长,传统的版本控制方式往往…...