首页 > 试题广场 >

复杂链表的复制

[编程题]复杂链表的复制

热度指数：769386 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例:

输入:{1,2,3,4,5,3,5,#,2,#}

输出:{1,2,3,4,5,3,5,#,2,#}

解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。

以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5

后半部分，3，5，#，2，#分别的表示为

1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null

如下图:

示例1

输入

{1,2,3,4,5,3,5,#,2,#}

输出

{1,2,3,4,5,3,5,#,2,#}

说明：本题目包含复杂数据结构ListNode、RandomListNode，点此查看相关信息

算法知识视频讲解

幸福的火龙果在干饭

发表于 2021-06-30 15:17:38

精华题解一、题目描述 JZ25 复杂链表的复制题目大意：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头节点注意审题：我们需要对链表进行深拷贝二、算法1（哈希表）解题思路假如链表没有随机指针, 展开全文

牛客题解官

发表于 2022-04-25 17:39:42

精华题解题目的主要信息：一个复杂链表除了有指向后一个节点的指针，还有一个指针随机节点的指针将该复杂链表拷贝，返回拷贝链表的头节点拷贝链表必须创建新的节点举一反三：学习完本题的思路你可以解决如下题目： JZ18. 删除链表的节点 JZ6. 从尾到头打印链表 JZ52. 两个链表的第一个公共节点展开全文

Maokt

发表于 2021-06-22 14:55:23

精华题解解题思路： 1、利用哈希表的查询特点，考虑构建原链表节点和新链表对应节点的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可 2、考虑构建原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼展开全文

牛客500979850号

发表于 2021-07-18 11:38:56

精华题解方法一：哈希表 1.使用一个哈希表来映射原节点和新节点 2.通过将原节点和新节点的键值对添加进去代表当前节点已经复制 3.利用next和random的指向递归遍历链表代码如下： class Solution { public: unordered_map<RandomListNode*, 展开全文

leaves0924

发表于 2021-06-22 16:20:18

精华题解题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。下图是一个含有5个结点的复杂链表。图中实线箭头表示ne 展开全文

一叶浮尘

发表于 2019-08-17 09:56:12

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）这道题目刚开始读起来没有思路，最后只能用比较笨拙的方法来实现，用map保留过曾经访展开全文

无名者

发表于 2020-03-15 22:04:52

看了前几个大佬的题解，感觉自己的挺容易理解的，具体注释应该能解释清楚 import java.util.HashMap; public class Solution { public RandomListNode Clone(RandomListNode pHead) { i 展开全文

jalr4ever

发表于 2019-08-31 17:54:05

剑指 - 复杂链表的复制题目输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）思路用一个 hashmap 建立新旧链表节点的对展开全文

小陆要懂云

发表于 2021-08-18 17:00:18

RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return nullptr; RandomListNode* cur = pHead; unordered_map<Random 展开全文

shaonian

发表于 2019-09-29 11:00:16

提供一个不一样的解法，O(n), O(n), 这道题只要能找到random指针的映射关系即可，可以考虑使用字典保存这种映射关系。把所有节点放在一个list里面，然后计算random的映射字典(位置->位置)，然后复制一个新的list，依次赋值next和random class Solution 展开全文

宫水三叶的刷题日记

发表于 2021-07-26 16:02:08

模拟 + 哈希表如果不考虑 random 指针的话，对一条链表进行拷贝，我们只需要使用两个指针：一个用于遍历原链表，一个用于构造新链表（始终指向新链表的尾部）即可。这一步操作可看做是「创建节点 + 构建 next 指针关系」。现在在此基础上增加一个 random 指针，我们可以将 next 指针展开全文

c7rious

发表于 2019-11-27 10:13:19

class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if (pHead == nullptr) return pHead; // map 展开全文

LaN666

发表于 2021-01-29 19:29:39

浅拷贝就是两者共用一份内存地址，一个改变，另外一个跟着改变；深拷贝就是两者的内存地址是不一样的，互相独立的。那么我们要怎么进行深拷贝呢？肯定不可以直接将节点赋值给新的节点，这样就是引用了。所以我想到的是新建节点，然后新节点的值跟原来的节点的一样。但是要怎么存储呢？因为我们深拷贝的新的链表，每一个展开全文