剑指offer：面试题35. 复杂链表的复制
题目：复杂链表的复制
请实现 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 <= 10000Node.random为空（null）或指向链表中的节点。- 节点数目不超过 1000 。
解题：
dfs
class Solution {
public:Node* copyRandomList(Node* head) {unordered_map used;return dfs(head, used);}Node* dfs(Node* head, unordered_map& used) {if (!head) return nullptr;if (used.count(head)) return used[head];Node *res = new Node(head->val);used[head] = res;res->next = dfs(head->next, used);res->random = dfs(head->random, used); return res;}
};
更多相关：
-
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 使用双指针的方式，各自构造一个大元素的头节点和小元素...
-
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1...
-
题目描述如下： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 很明显这个题目是206 反转链表的进阶版 需要记录第m-1个节点和第n+1个...
-
描述如下： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 方法一：原地反转 数据结构如下 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}...
-
二叉搜索树的编码和解码描述： 编码：即将一个二叉搜索树编码，节点数值转换为字符串 解码：即将一个字符串解码，数值转换为对应的二叉搜索树的节点 过程导图如下： 针对性编码实现如下: /*数字转字符串*/ void change_num_to_string(int val, string &tmp) {string buf;whil...
-
二叉搜索树又名二叉排序树。 大概简略的思维导图如下，方便记忆特性 基本二叉搜索树创建过程如下 /*数据结构如下*/ typedef struct tree {int data;struct tree *left = NULL;struct tree *right = NULL; }Tree,*TreeNode;/*Node 为二...
-
Linux安装Nodejs 阿里云镜像： https://npm.taobao.org/mirrors/node/ 选择所需版本，进行下载。 我这边下载的是：https://npm.taobao.org/mirrors/node/v8.2.1/node-v8.2.1-linux-x64.tar.gz ...
-
1. HDFS Architecture 一种Master-Slave结构。包括Name Node, Secondary Name Node,Data Node Job Tracker, Task Tracker。JobTrackers: 控制全部的Task Trackers 。这两个Tracker将会在MapReduce课程里...
-
下载Nodejs插件，下载zip压缩包后解压链接: http://pan.baidu.com/s/1hsBk60k 密码: jrcv打开Sublime Text3，点击菜单“首选项（N）” =>“浏览插件（B）”打开“Packages”文件夹，并将第1部的Nodejs文件夹剪切进来打开文件“Nodejs.sublime-build”，...
-
在使用空时，习惯这么赋值 int *p = NULL; 编译器进行解释程序时，NULL会被直接解释成0，所以这里的参数根本就不是大家所想的NULL，参数已经被编译器偷偷换成了0，0是整数。 因此这面的问题就尴尬了 不好意思图片引用于网络中。 为啥呢不是this is the ptr function…这个。这就是C++中的...
-
var d= {a: 1,b: null,c: 3,d: undefined };Object.keys(d).forEach(k=>d[k]==null&&delete d[k]);//去掉值为null或undefined的对象属性//Object.keys(d).forEach(k=>(d[k]==null||d[k]==='')...
-
//ES6获取浏览器url跟参 public getUrlParam = a => (a = location.search.substr(1).match(new RegExp(`(^|&)${a}=([^&]*)(&|$)`)),a?a[2]:null);...
-
文章目录1. 解决问题2. 应用场景3. 实现如下C++实现C语言实现4. 缺点 1. 解决问题 在简单工厂模式中，我们使用卖衣服进行举例，同一种工厂可以卖很多不同种类的衣服，工厂只是将衣服的生产过程进行了封装。 当我们增加衣服种类的时候，在简单工厂模式中需要修改工厂的代码，破坏了类的开闭原则（对扩展开发， 对修改关闭），...
-
在服务端数据库的处理当中，涉及中文字符的结构体字段，需要转为Utf8后再存储到表项中。从数据库中取出包含中文字符的字段后，如果需要保存到char *类型的结构体成员中，需要转为Ansi后再保存。从数据库中取出类型数字的字段后，如果需要保存到int型的结构体成员中，需要调用atoi函数进行处理后再保存。 1 static char *...