(刷题记录2)随机链表的复制

[刷题记录2]随机链表的复制

  • 题目信息:
  • 题目思路(环境来自力扣OJ的C语言):
  • 复杂度:
  • 代码和解释:
    • 1.遍历一遍原链表的同时,在每个原节点后面插入一个相同的新节点,共插入 n 个新节点。
    • 2.利用两者联系,当原节点 random 指向非空节点时,新节点 random 指向为原节点 random->next。
    • 3.将原链表和新链表分开。
  • 完整代码

题目信息:

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点

题目参考:
力扣:138. 随机链表的复制
牛客网:JZ35 复杂链表的复制

题目思路(环境来自力扣OJ的C语言):

1.遍历一遍原链表的同时,在每个原节点后面插入一个相同的新节点,共插入 n 个新节点。

2.利用两者联系,当原节点 random 指向非空节点时,新节点 random 指向为原节点 random->next。

3.将原链表和新链表分开。

复杂度:

时间复杂度:O(n)
空间复杂度:O(1)
空间复杂度考虑的是算法本身使用的空间消耗,题目中由于拷贝产生的O(n)空间为题目本身要求,则不计入。

代码和解释:

1.遍历一遍原链表的同时,在每个原节点后面插入一个相同的新节点,共插入 n 个新节点。

typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)								// 为空直接返回
        return NULL;
        
    Node* cur = head;
    while (cur)      			// 当cur == NULL时退出           
    {
        Node* temp = (Node*)malloc(sizeof(Node));	// 1.创建新节点
        temp->val = cur->val;   					// 并拷贝值
        temp->next = cur->next;	// 2.将新节点temp->next 指向 cur->next
        cur->next = temp;		// 3.将cur->next 指向 temp

        cur = temp->next;		// 4.cur移动到temp->next的位置
    }


}

在这里插入图片描述

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

2.利用两者联系,当原节点 random 指向非空节点时,新节点 random 指向为原节点 random->next。

    cur = head;                                     // cur 回到头节点
    while (cur)                                     // 拷贝 random
    {
        if (cur->random == NULL)                    // 1.当cur->random为空
            cur->next->random = NULL;               // 置空
        else
            cur->next->random = cur->random->next;  // 2.当cur->random不为空

        // 可用三目操作符简写成下式
        // cur->next->random = (cur->random ? cur->random->next : NULL);

        cur = cur->next->next;                      // 3.移动到下一个原节点
    }

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

3.将原链表和新链表分开。

    cur = head;                                     // cur 回到头节点
    Node* newHead = head->next;                     // 1.保存新节点的头
    Node* temp = newHead;
    while (cur)                                     // 将两个链表复原
    {
        cur->next = temp->next;                     // 2.恢复原节点next指向
        cur = cur->next;                            // 2.2.移动到下一个原节点

        temp->next = (cur ? cur->next : cur);       // 3.恢复新节点next指向
        temp = temp->next;                          // 3.2.移动到下一个新节点
    }

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

完整代码

typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)								// 为空直接返回
        return NULL;
        
    Node* cur = head;
    while (cur)      			// 当cur == NULL时退出           
    {
        Node* temp = (Node*)malloc(sizeof(Node));	// 1.创建新节点
        temp->val = cur->val;   					// 并拷贝值
        temp->next = cur->next;	// 2.将新节点temp->next 指向 cur->next
        cur->next = temp;		// 3.将cur->next 指向 temp

        cur = temp->next;		// 4.cur移动到temp->next的位置
    }

    cur = head;                                     // cur 回到头节点
    while (cur)                                     // 拷贝 random
    {
        if (cur->random == NULL)                    // 1.当cur->random为空
            cur->next->random = NULL;               // 置空
        else
            cur->next->random = cur->random->next;  // 2.当cur->random不为空

        // 可用三目操作符简写成下式
        // cur->next->random = (cur->random ? cur->random->next : NULL);

        cur = cur->next->next;                      // 3.移动到下一个原节点
    }

    cur = head;                                     // cur 回到头节点
    Node* newHead = head->next;                     // 1.保存新节点的头
    Node* temp = newHead;
    while (cur)                                     // 将两个链表复原
    {
        cur->next = temp->next;                     // 2.恢复原节点next指向
        cur = cur->next;                            // 2.2.移动到下一个原节点

        temp->next = (cur ? cur->next : cur);       // 3.恢复新节点next指向
        temp = temp->next;                          // 3.2.移动到下一个新节点
    }

    return newHead;         // 返回新节点的头
}

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

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

相关文章

神奇的Vue3 - 组件探索

神奇的Vue3 第一章 神奇的Vue3—基础篇 第二章 神奇的Vue3—Pinia 文章目录 神奇的Vue3了解组件一、注册组件1. 全局注册​2. 局部注册3. 组件命名 二、属性详解1. Props(1)基础使用方法(2)数据流向:单项绑定原则&…

ThreeJS:Mesh网格与三维变换

Mesh网格 ThreeJS中,Mesh表示基于以三角形为多边形网格(polygon mesh)的物体的类,同时也作为其它类的基类。 通过Mesh网格,我们可以组合Geometry几何体与Material材质属性,在3D世界中,定义一个物体。例如:之…

vue2(4)之scoped解决样式冲突/组件通信/非父子通信/ref和$refs/异步更新/.sync/事件总线/provide和inject

vue2 一、学习目标1.组件的三大组成部分(结构/样式/逻辑)2.组件通信3.综合案例:小黑记事本(组件版)4.进阶语法 二、scoped解决样式冲突**1.默认情况**:2.代码演示3.scoped原理4.总结 三、data必须是一个函数…

Copilot Venture Studio創始合伙人楊林苑確認出席“邊緣智能2024 - AI開發者峰會”

隨著AI技術的迅猛發展,全球正逐步進入邊緣計算智能化與分布式AI深度融合的新時代,共同書寫著分布式智能創新應用的壯麗篇章。邊緣智能,作為融合邊緣計算和智能技術的新興領域,正逐漸成為推動AI發展的關鍵力量。借助分布式和去中心…

由于找不到mfc140u.dll,无法继续执行的多种解决方法

在我们日常与计算机的密切互动中,或许不少用户都曾遇到过这样一个棘手的问题:系统突然弹出一个提示窗口,告知我们“找不到mfc140u.dll文件”。这个文件是Microsoft Foundation Class(MFC)库的一部分,用于支…

提升编码技能:学习如何使用 C# 和 Fizzler 获取特价机票

引言 五一假期作为中国的传统节日,也是旅游热门的时段之一,特价机票往往成为人们关注的焦点。在这个数字化时代,利用爬虫技术获取特价机票信息已成为一种常见的策略。通过结合C#和Fizzler库,我们可以更加高效地实现这一目标&…

20240502在WIN10下给X99平台上的M6000显卡安装驱动程序

20240502在WIN10下给X99平台上的M6000显卡安装驱动程序 2024/5/2 9:32 人工智能计算领域的领导者 | NVIDIA https://www.nvidia.cn/ C:\NVIDIA\DisplayDriver\552.22\Win11_Win10-DCH_64\International IMPORTANT NOTICE -- READ CAREFULLY: -------------------------------…

pmp培训机构哪个比较好,求推荐-

寻找一个自己认为比较好的PMP培训机构千万不要盲目,先在网上看看大家都推荐什么,看一下各个机构的老学员反馈,这些对我们的选择有非常大的帮助,最起码有了一些风评上的参考,现状就是目前线上机构的竞争比较大&#xff…

c语言从入门到函数速成(1)

温馨提醒:本篇文章适合人群:刚学c又感觉那个地方不怎么懂的同学以及以及学了一些因为自身原因停学一段时间后又继续学c的同学 好,正片开始。 主函数 学c时最先学的是我们c语言程序的主体函数,c的主函数有两种写法,这…

【JavaEE】Thread的方法和属性

文章目录 1、Thread的常见构造方法2、Thread的几个常见属性2.1 ID2.2 名称2.3 状态2.4 优先级2.5 是否后台线程2.6 是否存活2.7 是否被中断 3.补充说明3.1 Thread.sleep()的作用3.2 Thread.sleep()的异常处理方式 1、Thread的常见构造方法 方法说明Thread()创建线程对象Thread…

动态规划-子序列问题1

文章目录 1. 最长递增子序列(300)2. 摆动序列(376)3. 最长递增子序列的个数(673)4. 最长数对链(646) 1. 最长递增子序列(300) 题目描述: 状态表…

Linux 进程间通信之命名管道

💓博主CSDN主页:麻辣韭菜💓   ⏩专栏分类:Linux知识分享⏪   🚚代码仓库:Linux代码练习🚚   🌹关注我🫵带你学习更多Linux知识   🔝 目录 前言 命名管道 创建一个命名管道 …

LeetCode题练习与总结:删除排序链表中的重复元素--83

一、题目描述 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 示例 1: 输入:head [1,1,2] 输出:[1,2]示例 2: 输入:head [1,1,2,3,3] 输…

袁庭新ES系列17节|Spring Data Elasticsearch基础

前言 为了简化对Elasticsearch的操作Spring Data提供了Spring Data Elasticsearch。Spring Data Elasticsearch是Spring Data技术对Elasticsearch原生API封装之后的产物,它通过对原生API的封装,使得程序员可以简单的对Elasticsearch进行各种操作。接下来…

InfluxDB安装使用介绍

1.介绍 InfluxDB是一个由InfluxData开发的开源时序型数据。它由Go写成,着力于高性能地查询与存储时序型数据。InfluxDB被广泛应用于存储系统的监控数据,IoT行业的实时数据等场景。 2.对常见关系型数据库(MySQL)的基础概念对比 1…

满上! —— 十年之约#22(ROI 48%)

原创 | 刘教链 空头在忍耐了很久之后,趁五一劳动节东方放假发动突袭,把BTC(比特币)打到6万刀以下。这使得我们终于终结了7个月七连涨的趋势,确定4月以收跌结束。 4月开盘70k,最高72.8k,最低59.6…

CPU卡园区码分析计算,根据卡号计算外部密码

生活中我们可能遇到这种情况,比如家里的门禁卡丢失了,拿着家里人的去街上 复制,结果对方说无法复制,因为这种卡是CPU卡的一种,必须知道园区码才可以成功复制,这个时候,我们就需要请出我们的战神…

uniapp实现点击事件跳转页面

首先定义一个点击事件 这里采用的vue3的写法,然后写上触发事件后要跳转的路径 function jump() {uni.switchTab({url:/pages/bangong/index})} 到这里就简单的实现uniapp的点击跳转页面了

开源农场管理软件

软件介绍 Tania是一款基于Go、Vue.JS和SQLite的开源农场日记软件。该项目始于2016年11月,由于无法找到适合自己需求的软件,开发团队决定自己搭建一套适合家庭后院花园的管理系统,并可以随时随地进行管理。 项目功能描述 Tania是一款免费且开源…

密码学基础练习五道 RSA、elgamal、elgamal数字签名、DSA数字签名、有限域(GF)上的四则运算

1.RSA #include <stdlib.h>#include <stdio.h>#include <string.h>#include <math.h>#include <time.h>#define PRIME_MAX 200 //生成素数范围#define EXPONENT_MAX 200 //生成指数e范围#define Element_Max 127 //加密单元的…