C语言复杂链表的复制实例详解

目录
  • 一、题目描述
    • 示例1：
    • 示例2：
    • 示例3：
    • 示例4：
  • 二、思路分析
  • 三、整体代码
  • 总结

一、题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2：

输入：head = [[1,1],[2,1]]

输出：[[1,1],[2,1]]

示例3：

输入：head = [[3,null],[3,0],[3,null]]

输出：[[3,null],[3,0],[3,null]]

示例4：

输入：head = []

输出：[]解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000

Node.random 为空(null)或指向链表中的节点。

节点数目不超过 1000 。

二、思路分析

注：思路分析中的一些内容和图片参考自力扣各位前辈的题解，感谢他们的无私奉献

分析

复制普通链表：给定链表的头结点head，复制普通链表很简单，只需遍历链表，每轮需要：建立新结点 + 让前驱结点的next指向当前这个新结点 + 让当前这个新结点的next指向空

复制复杂链表：本题链表的结点新增了 random 指针，指向链表中的任意结点或者null。这个 random 指针意味着在复制过程中，除了构建前驱结点的next指针，还要构建前驱结点的ramdom指针。因此，每轮需要：建立2个新结点 + 让前驱结点的next指向第1个新结点 + 让前驱结点的random指向第2个新结点。但是这有一个问题：并不是每次都需要建立2个新结点。有时候前驱结点的random指向的是已经存在的结点，但是如何判断出来呢？如果把所有结点遍历一遍，那就太麻烦了。

思路

利用哈希表的查询特点，考虑构建原链表结点和新链表对应结点的键值对映射关系，再遍历构建新链表各结点的next和random引用指向即可。

算法流程：

①若头节点head为空结点，直接返回NULL ；

②初始化：声明一个哈希表dic，定义一个结点cur指向头结点，这个cur控制后面的循环

③建立哈希映射：遍历这个链表，每个链表结点对应建立一个新结点，并向dic添加键值对(原cur结点, 新cur结点)

④构建新链表的引用指向：构建新结点的next和random引用指向

⑤返回值： 返回新链表的头结点，即dic[cur]

三、整体代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        //若是空链表，则返回NULL
        if(head == NULL) return NULL;
        //创建一个结点，指向这个链表的头结点。这个结点用来控制后面的循环
        Node* cur = head;
        //创建一个哈希表
        unordered_map<Node*, Node*> map;
        while(cur != NULL){
            //为链表每个结点创建一个对应的新结点，并建立原结点和新结点的Map映射
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        //为新链表每个结点的next和random设置对应的指向
        while(cur != NULL){
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        //返回新链表的头结点
        return map[head];
    }
};

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容!

赞 (0)

相关推荐

  • C语言数据结构超详细讲解单向链表

    C语言数据结构超详细讲解单向链表

    目录 1.链表概况 1.1 链表的概念及结构 1.2 链表的分类 2. 单向链表的实现 2.1 SList.h(头文件的汇总,函数的声明) 2.2 SList.c(函数的具体实现逻辑) 2.2.1 打印链表 2.2.2 搞出一个新节点(为其他函数服务) 2.2.3 链表尾插 2.2.4 链表头插 2.2.5 链表尾删 2.2.6 链表头删 2.2.7 查找节点 2.2.8 在pos位置之前插入 2.2.9 在pos位置之后插入 2.2.10 删除pos位置 2.2.11 删除pos之后位置 2.

  • C语言实现带头双向循环链表

    C语言实现带头双向循环链表

    目录 前言 1. 创建结构体 2.malloc新节点 3.创建哨兵位节点 4.尾插 5.打印 6.尾删 7.头插 8.在指定位置pos的前面进行插入 9. 删除指定位置pos节点 10.销毁链表 前言 在实际生活中最常用的就是这两种链表.无头单向非循环链表.和带头双向循环链表.无头单向非循环链表:结构简单,一般不会单独用来存数据.实际中更多是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.另外这种结构在笔试面试中出现很多.带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数

  • C语言 超详细模拟实现单链表的基本操作建议收藏

    C语言 超详细模拟实现单链表的基本操作建议收藏

    目录 1 链表的概念及结构 2 链表的分类 3 链表的实现无头+单向+非循环链表增删查改实现 3.1 链表的定义 3.2 链表数据的打印 3.3 链表的尾插 3.4 链表空间的动态申请 3.5 链表的头插 3.6 链表的尾删 3.7 链表的头删 3.8 链表任意位置的前插入 3.9 链表任意位置的后插入 3.10 链表的任意位置的删除 3.11 链表的任意位置的前删除 3.12 链表的任意位置的后删除 3.13 链表的销毁 3.14 链表的总结 1 链表的概念及结构 概念:链表是一种物理存储结构

  • C语言数据结构实例讲解单链表的实现

    C语言数据结构实例讲解单链表的实现

    目录 1.单链表 2.单链表的实现 头文件 函数的实现 (1)打印链表 (2)动态申请结点 (3)尾插 (4)头插 (5)尾删 (6)头删 (7)查找 (8)在pos之前插入 (9)删除pos (10)在pos之后插入 (11)在pos后删除 (12)最后用完记得销毁 3.各功能的测试 这里我们来简单实现单链表的增删查找. 1.单链表 概念:链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 . (链表和我们生活中最接近的就是火车了.) 2.单链

  • C语言结构体使用之链表

    C语言结构体使用之链表

    目录 一.结构体的概念 二.结构体的用法 三.结构体数组和指针 四.结构体指针 五.包含结构体的结构体 六.链表 七.静态链表 八.动态链表 一.结构体的概念 比如说学生的信息,包含了学生名称.学号.性别.年龄等信息,这些参数可能有些是数组型.字符型.整型.甚至是结构体类型的数据.虽然这些都是不同类型的数据,但是这些都是用来表达学生信息的数据. 二.结构体的用法 1.struct 结构体名称 访问方法: 结构体变量名.成员 {undefined 成员1: 成员2: }: 2. typedef s

  • C语言 推理证明带环链表详细过程

    C语言 推理证明带环链表详细过程

    目录 什么是带环链表: 判断链表是否带环: 环形链表 I 找带环形链表入环的第一个结点: 环形链表 II 什么是带环链表: 带环链表是链表最后一个结点的指针域不是指向空指针,而是指向链表之前的结点,这样就形成了环状的链表结构. 如图所示: 判断链表是否带环: 那么问题来了,如何判断一个链表是否带环呢? 这里我们再次运用了快慢指针,但是快慢指针又该如何具体设置呢? 判断思路: 先定义一个快指针fast,一个慢指针slow. 快指针一定是比慢指针先进环的,当slow进环时,fast指针便开始了追sl

  • C语言实现无头单链表详解

    C语言实现无头单链表详解

    目录 链表的结构体描述(节点) 再定义一个结构体(链表) 断言处理 & 判空处理 创建链表 创建节点 头插法 打印链表 尾插法 指定位置插入 头删法 尾删法 指定位置删除 查找链表 删除所有指定相同的元素 总结 再封装的方式,用 c++ 的思想做无头链表 链表的结构体描述(节点) #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; //节点 typede

  • C语言复杂链表的复制实例详解

    C语言复杂链表的复制实例详解

    目录 一.题目描述 示例1: 示例2: 示例3: 示例4: 二.思路分析 三.整体代码 总结 一.题目描述 请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 示例1: 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例2: 输

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • C语言文件复制实例详解

    C语言文件复制实例详解

    C语言文件复制实例详解 文件复制,在Linux中,将生成的read.o 重新文件拷贝一份复制到ReadCopy.o中,并且更改ReadCopy.o文件的操作权限.使其能够正常运行. 实例代码: #include <stdio.h> int main(){ FILE *r_file = fopen ("read.o","rb"); FILE *w_file = fopen ("ReadCopy.o","w"); ch

  • C语言树状数组的实例详解

    C语言树状数组的实例详解 最近学了树状数组,给我的感觉就是 这个数据结构好神奇啊^_^ 首先她的常数比线段树小,其次她的实现复杂度也远低于线段树 (并没有黑线段树的意思=-=) 所以熟练掌握她是非常有必要的.. 关于树状数组的基础知识与原理网上一搜一大堆,我就不赘述了,就谈一些树状数组的应用好了 1,单点修改,求区间和 #define lowbit(x) (x&-x) // 设 x 的末尾零的个数为 y , 则 lowbit(x) == 2^y void Update(int i,int v)

  • Kotlin 语言中调用 JavaScript 方法实例详解

    Kotlin 语言中调用 JavaScript 方法实例详解 Kotlin 已被设计为能够与 Java 平台轻松互操作.它将 Java 类视为 Kotlin 类,并且 Java 也将 Kotlin 类视为 Java 类.但是,JavaScript 是一种动态类型语言,这意味着它不会在编译期检查类型.你可以通过动态类型在 Kotlin 中自由地与 JavaScript 交流,但是如果你想要 Kotlin 类型系统的全部威力 ,你可以为 JavaScript 库创建 Kotlin 头文件. 内联 J

  • C语言中联合体union的实例详解

     C语言中联合体union的实例详解 1.定义: union(int i, short s, char c) un; un.i = 3; printf("i=%d",un.i); printf("length = %d\n",sizeof(un);//==4,有最大的变量来决定 2.相当与java里的List T类型 3.数据交换 void swap(int *p , int *q){ int temp = *p; *p = *q; *q = temp; } 4.打

  • C语言中二级指针的实例详解

    C语言中二级指针的实例详解

    C语言中二级指针的实例详解 用图说明 示例代码: #include <stdio.h> int main(int argc, const char * argv[]) { // int a = 5; int *p1 = &a; //-打印地址-----地址相同--------------- printf("&a = %p\n", &a);// printf("p1 = %p\n", p1);// int **p2 = &p

  • C语言中调用Swift函数实例详解

    C语言中调用Swift函数实例详解 在Apple官方的<Using Swift with Cocoa and Objectgive-C>一书中详细地介绍了如何在Objective-C中使用Swift的类以及如何在Swift中使用Objective-C中的类.在后半部分也介绍了如何在Swift中使用C函数,不过对于如何在C语言中使用Swift函数却只字未提.这里我就为大家分享一下如何在C语言中调用Swift函数. 我们首先要知道的是,所有Swift函数都属于闭包.其次,Swift函数的调用约定与

  • Javascript复制实例详解

    在做项目时有一个需求,是需要复制内容到剪切板,因为有众多浏览器,所以要兼容性很重要. 1.最简单的copy,只能在IE下使用 使用clipboardData方法 <script type="text/javascript"> function copy(){ window.clipboardData.setData("text",document.getElementById("name").value); alert("T

  • C语言实现“幸运数”的实例详解

    C语言实现“幸运数”的实例详解

    C语言实现"幸运数"的实例详解 1.题目: 标题:幸运数 幸运数是波兰数学家乌拉姆命名的.它采用与生成素数类似的"筛法"生成. 首先从1开始写出自然数1,2,3,4,5,6,-. 1 就是第一个幸运数. 我们从2这个数开始.把所有序号能被2整除的项删除,变为: 1 _ 3 _ 5 _ 7 _ 9 -. 把它们缩紧,重新记序,为: 1 3 5 7 9 -. .这时,3为第2个幸运数,然后把所有能被3整除的序号位置的数删去.注意,是序号位置,不是那个数本身能否被3整除!

随机推荐