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

【Leedcode】数据结构中链表必备的面试题(第五期)

【Leedcode】数据结构中链表必备的面试题(第五期)


文章目录

  • 【Leedcode】数据结构中链表必备的面试题(第五期)
    • 1.题目
    • 2.思路+图解
      • (1)第一步:复制每一个结点,插入到原结点和下一个结点之间
      • (2)第二步:根据原结点random,处理复制结点的random
      • (2)第三步:复制结点解下来连接成一个新链表,恢复原链表链接关系
    • 3.整体源代码
  • 总结


1.题目

  1. 复制带随机指针的链表: 如下(示例):
给你一个长度为n的链表,每个节点包含一个额外增加的随机指针random,该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。
新节点的next指针和random指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。
复制链表中的指针都不应指向原链表中的节点 。  返回复制链表的头节点。

简单来说:复制原来的链表(新的),返回新链表的头结点


在这里插入图片描述


在这里插入图片描述


2.思路+图解

(1)第一步:复制每一个结点,插入到原结点和下一个结点之间

在这里插入图片描述


第一步代码实现 : 如下(示例):

//1.第一步:先把原来的拷贝一份struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy -> next = cur -> next;cur -> next = copy;copy -> val = cur -> val;cur = copy -> next;}

(2)第二步:根据原结点random,处理复制结点的random

这里要注意:复制完之后的random所指向的是复制之前random的next,具体如下图


在这里插入图片描述


在这里插入图片描述


第二步代码实现 : 如下(示例):

// 2.第二步:把random拷贝过去cur = head; while(cur){struct Node* copy = cur -> next;if(cur -> random == NULL){copy -> random = NULL;}else{copy -> random = cur -> random -> next;}cur = copy -> next;}

(2)第三步:复制结点解下来连接成一个新链表,恢复原链表链接关系

在这里插入图片描述


在这里插入图片描述


第三步代码实现 : 如下(示例):

 // 3.第三步:把拷贝结点解下来,链接成新的链表,同时恢复原链表cur = head;struct Node* copyhead = NULL ,*copytail =NULL;while(cur){struct Node* copy = cur -> next;struct Node* next = copy -> next;if(copytail == NULL){copytail = copyhead = copy;}else{copytail -> next = copy;copytail = copy;}//恢复原链表的犍cur -> next = next;cur = next ;}

3.整体源代码

整体源代码 : 如下(示例):

struct Node 
{int val;struct Node *next;struct Node *random;
};
struct Node* copyRandomList(struct Node* head) 
{//1.第一步:先把原来的拷贝一份struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy -> next = cur -> next;cur -> next = copy;copy -> val = cur -> val;cur = copy -> next;}// 2.第二步:把random拷贝过去cur = head; while(cur){struct Node* copy = cur -> next;if(cur -> random == NULL){copy -> random = NULL;}else{copy -> random = cur -> random -> next;}cur = copy -> next;}// 3.第三步:把拷贝结点解下来,链接成新的链表,同时恢复原链表cur = head;struct Node* copyhead = NULL ,*copytail =NULL;while(cur){struct Node* copy = cur -> next;struct Node* next = copy -> next;if(copytail == NULL){copytail = copyhead = copy;}else{copytail -> next = copy;copytail = copy;}//恢复原链表的犍cur -> next = next;cur = next ;}return copyhead;
}

总结

以上就是今天要讲的内容,本文介绍了【Leedcode】数据结构中链表必备的面试题(第五期)。
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!
在这里插入图片描述

相关文章:

【Leedcode】数据结构中链表必备的面试题(第五期)

【Leedcode】数据结构中链表必备的面试题(第五期) 文章目录【Leedcode】数据结构中链表必备的面试题(第五期)1.题目2.思路图解(1)第一步:复制每一个结点,插入到原结点和下一个结点之…...

ECDH secp256k1 集成

在Android 原生api是不支持secp256k1算法的,所以要先集成以下库:implementation com.madgag.spongycastle:core:1.58.0.0compile com.madgag.spongycastle:prov:1.54.0.0compile com.madgag.spongycastle:pkix:1.54.0.0compile com.madgag.spongycastle:…...

工单模型的理解与应用

工单(任务单)模型的定义 工单模型是一种分派任务的方法,可以用来跟踪、评估和报告任务的完成情况。它通常用于针对特定目标的重复性任务或项目,以确保任务能够按时完成并符合期望的标准。   工单模型的基本流程为:提…...

Python年利率计算器【N日年化收益率】

现在有闲钱的人,按照聪明等级从低到高排序应该是钱买股票,一年利率约为-20%钱放银行活期,年利率约为0.3%钱放银行定期,一年利率约为1.5%钱放余额宝(支付宝)或零钱通(微信)&#xff0…...

3年测试拿8K,被校招来的实习生反超薪资,其实你在假装努力

最近朋友给我分享了一个他公司发生的事 大概的内容呢:公司一位工作3年的测试工资还没有新人高,对此怨气不小,她来公司辛辛苦苦三年,三年内迟到次数都不超过5次,每天都是按时上下班,工作也按量完成&#xf…...

因子分析计算权重

因子分析两类权重计算方法总结 案例背景 疫情爆发以来,越来越多的人为了避免线下与人接触,选择了线上购买生活必需品。网购虽然方便快捷,但是随着订单压力的增加,物流问题也随之出现,近期有很多卖家收到物流投诉的问题…...

国家调控油价预测案例+源码

项目git地址:https://github.com/Boris-2021/Oil-price-control-forecast 使用已知的历史数据:日期、汇率、布伦特、WTI、阿曼原油价格,预测下一个调价周期中的汽油、柴油零售限价的调价价格。 一. 需求 1.1 需求说明 使用已知的历史数据&a…...

Gephi快速入门

Gephi快速入门1. 导入文件(Import file)2. 布局(Layout)3. 排序(Ranking)4. 指标(Metrics)5. 标签(Label)6. 社区发现(Community detection&#…...

GitHub

什么是 Github?GitHub是一个面向开源及私有软件项目的托管平台,因为只支持Git作为唯一的版本库格式进行托管,故名GitHub。一、常用词Watch:观察。如果watch了一个项目,之后这个项目有更新,你会在第一时间收到该项目更…...

QT基础入门【调试篇】QT远程部署与调试嵌入式ARM开发板

目录 一、环境配置 1、根据开发板完成交叉编译链以及GDB的配置(因开发板而异)...

可观测性最佳实践|阿里云事件总线 EventBridge 最佳实践

本文介绍如何把阿里云事件总线 EventBridge 的内容接入观测云平台,通过观测云强大的统一汇聚能力轻松获取阿里云事件,实时追踪最新的数据信息。 背景信息 事件总线 EventBridge 是阿里云提供的一款无服务器事件总线服务,支持阿里云服务、自定…...

设计模式-行为型

设计模式-行为型 行为型设计模式主要用于软件运行时复杂的流程控制。包含:模板方法模式、策略模式、命令模式、职责链模式、状态模式、观察者模式、中介者模式、迭代器模式、访问者模式、备忘录模式和解释器模式 模板方法模式 在软件设计时,很多时候系…...

Salesforce大揭秘!SaaS鼻祖不为人知的那些事!

Salesforce的世界无疑是广阔的。自从创始人Marc Benioff于1999年创立公司以来,Salesforce一直在打破CRM领域的界限,改变销售、营销和技术的格局。 作为全球领先的B2B科技公司之一,Salesforce和硅谷里的其他企业一样,缔造着一个关…...

Oracle——物化视图

文章目录含义物化视图的语法物化视图的创建1、自动刷新的物化事务 ON COMMIT2、非自动刷新的物化视图 ON demand关于手动刷新物化视图的删除资料参考含义 什么是物化视图? 物化视图,通俗点说就是物理化的视图。 什么叫物理化? 将视图以表结构…...

ur3+robotiq 2f 140配置moveit

ur3robotiq 2f 140配置moveit 参考链接1 参考链接2 官方配置movit教程 搭建环境: ubuntu: 20.04 ros: Nonetic sensor: robotiq_ft300 gripper: robotiq_2f_140_gripper UR: UR3 reasense: D435i 通过下面几篇博客配置好了ur3、力传感器、robotiq夹爪…...

LDO 芯片烫手,问题出在哪里?

设计失误的一个电路,该电路是数字电路的电源,为图方便对12V直接通过线性电源芯片降压到5V: 图1:线性电源降压12V转5V 几块电路板打样好后,测试均发现AMS1117-5.0芯片烫手,负载电流100mA多,也满…...

零日漏洞发展格局及防御策略

在过去的一年半中, 在野利用的零日漏洞数量持续飙升 ,这些软件制造商尚不知晓的漏洞正在被国家行为体黑客组织和勒索软件团伙滥用。 今年上半年,Google Project Zero统计了近20个零日漏洞,其中 大部分针对微软、苹果和谷歌构建的…...

RabbitMQ 可用磁盘空间报警

概要当磁盘可用空间低于设定的值(默认50M),将触发警报,并阻塞所有生产者。这目标是为了避免填满整个磁盘,这将导致所有节点上的写入操作失败,并可能导致RabbitMQ停止服务。如何工作为了减少磁盘被填满的风险…...

Web前端学习:二

二一&#xff1a;文字font-size样式 font-size&#xff1a;**px 控制文字大小&#xff0c;可精准控制大小 默认样式medium&#xff0c;中等的 large&#xff0c;大一号 x-large&#xff0c;再大一号 xx-large&#xff0c;再大一号 small&#xff0c;小一号 <!DOCTYPE html…...

【第一章 计算机网络体系结构,标准化工作相关组织,性能指标,分层结构,OSI参考模型】

第一章 计算机网络体系结构&#xff0c;标准化工作相关组织&#xff0c;性能指标&#xff0c;分层结构&#xff0c;OSI参考模型 1.计算机网络&#xff1a; &#xff08;1&#xff09;概念&#xff1a; ①计算机网络是将一个分散的、具有独立功能的计算机系统&#xff0c;通过通…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...