A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) { }
};
============
这个链表节点和普通链表的区别就是,有一个random指针,可以指向链表中的任何元素或者为nullptr
返回产生一个深copy.
思路:
第一遍,对list的每一个节点复制一次放在节点后面,这一次只复制节点的next指针,不复制节点的random指针
第一遍结束后我们的链表节点
a->b->c->d... 会变成a->fake_a->b->fake_b->c->fake_c->d->d->fake_d....
第二遍再对链表进行random指针复制
第三遍堆链表进行拆分,这样的我们可以将链表分离出来一个新的链表.
code如下:
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head){
RandomListNode *curr = head;
while(curr){
RandomListNode *node = new RandomListNode(curr->label);
node->next = curr->next;
curr->next = node;
curr = node->next;
}///a->f_a-> b->f_b-> ...
curr = head;
while(curr){
if(curr->random){
curr->next->random = curr->random->next;
}
curr = curr->next->next;
} ///partition it into two linktable
RandomListNode dummy(-);
RandomListNode *h = &dummy;
curr = head;
while(curr){
h->next = curr->next;
curr->next = curr->next->next;
h = h->next;
curr = curr->next;
}
h->next = nullptr;
return dummy.next;
}
};
138. Copy List with Random Pointer的更多相关文章
-
133. Clone Graph 138. Copy List with Random Pointer 拷贝图和链表
133. Clone Graph Clone an undirected graph. Each node in the graph contains a label and a list of it ...
-
[LeetCode] 138. Copy List with Random Pointer 拷贝带有随机指针的链表
A linked list is given such that each node contains an additional random pointer which could point t ...
-
leetcode 138. Copy List with Random Pointer ----- java
A linked list is given such that each node contains an additional random pointer which could point t ...
-
【LeetCode】138. Copy List with Random Pointer
题目: A linked list is given such that each node contains an additional random pointer which could poi ...
-
138. Copy List with Random Pointer (Graph, Map; DFS)
A linked list is given such that each node contains an additional random pointer which could point t ...
-
Java for LeetCode 138 Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point t ...
-
138. Copy List with Random Pointer (not do it by myself)
A linked list is given such that each node contains an additional random pointer which could point t ...
-
[LeetCode] 138. Copy List with Random Pointer 拷贝带随机指针的链表
A linked list is given such that each node contains an additional random pointer which could point t ...
-
138 Copy List with Random Pointer 复制带随机指针的链表
给出一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点.返回一个深拷贝的链表. 详见:https://leetcode.com/problems/copy-list- ...
随机推荐
-
[译]:Xamarin.Android平台功能——位置服务
返回索引目录 原文链接:Location Services. 译文链接:Xamarin.Android平台功能--位置服务 本部分介绍位置服务以及与如何使用位置提供商服务 Location Servi ...
-
GO语言面向对象
当初开发go语言的时候就是因为C++的特性太过于繁杂,从而使得很多C++的开发者因为C++的特性而头疼,go语言成功的精简了C++的特性,使其很简洁,很少的特性,却可以完成很多的事情. go语言中并没 ...
-
[译]Mongoose指南 - Population
MongoDB没有join, 但是有的时候我们需要引用其它collection的documents, 这个时候就需要populate了. 我们可以populate单个document, 多个docum ...
-
Druid(准)实时分析统计数据库——列存储+高效压缩
Druid是一个开源的.分布式的.列存储系统,特别适用于大数据上的(准)实时分析统计.且具有较好的稳定性(Highly Available). 其相对比较轻量级,文档非常完善,也比较容易上手. Dru ...
-
AutoMapper使用
1.安装 现在AutoMapper已经更新到5.0版本了,可查看 http://www.nuget.org/packages/AutoMapper/ 我环境是4.0的,nuget安装 http://w ...
-
7 libjpeg使用
一.交叉编译libjepg编译 tar xzf libjpeg-turbo-1.2.1.tar.gz ./configure –help ./configure --prefix=/work/proj ...
-
Day4_装饰器
装饰器: #模板def auth(func): def wrapper(*args,**kwargs): res=func(*args,**kwargs) return res return wrap ...
-
MVC动态绑定下拉框
Controller: //获取下拉信息表 //_vendorsAppService.GetAllObj() 是获取下拉列表结果集 ViewData["vendlist"] = n ...
-
UOJ#349. 【WC2018】即时战略
原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ349.html 题解 被cqz D没了.我D cly 关你啥事(逃 首先链的情况直接rand就好了. 期望 ...
-
微软官网tools
DHCP/AD域插件: 远程管理工具(含DHCP/AD域) 安装网址: https://www.microsoft.com/zh-cn/download/details.aspx?id=7887 程序 ...