138. Copy List with Random Pointer

时间:2022-10-15 10:44:39

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的更多相关文章

  1. 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 ...

  2. [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 ...

  3. 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 ...

  4. 【LeetCode】138. Copy List with Random Pointer

    题目: A linked list is given such that each node contains an additional random pointer which could poi ...

  5. 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 ...

  6. 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 ...

  7. 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 ...

  8. [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 ...

  9. 138 Copy List with Random Pointer 复制带随机指针的链表

    给出一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点.返回一个深拷贝的链表. 详见:https://leetcode.com/problems/copy-list- ...

随机推荐

  1. [译]:Xamarin.Android平台功能——位置服务

    返回索引目录 原文链接:Location Services. 译文链接:Xamarin.Android平台功能--位置服务 本部分介绍位置服务以及与如何使用位置提供商服务 Location Servi ...

  2. GO语言面向对象

    当初开发go语言的时候就是因为C++的特性太过于繁杂,从而使得很多C++的开发者因为C++的特性而头疼,go语言成功的精简了C++的特性,使其很简洁,很少的特性,却可以完成很多的事情. go语言中并没 ...

  3. [译]Mongoose指南 - Population

    MongoDB没有join, 但是有的时候我们需要引用其它collection的documents, 这个时候就需要populate了. 我们可以populate单个document, 多个docum ...

  4. Druid(准)实时分析统计数据库——列存储+高效压缩

    Druid是一个开源的.分布式的.列存储系统,特别适用于大数据上的(准)实时分析统计.且具有较好的稳定性(Highly Available). 其相对比较轻量级,文档非常完善,也比较容易上手. Dru ...

  5. AutoMapper使用

    1.安装 现在AutoMapper已经更新到5.0版本了,可查看 http://www.nuget.org/packages/AutoMapper/ 我环境是4.0的,nuget安装 http://w ...

  6. 7 libjpeg使用

    一.交叉编译libjepg编译 tar xzf libjpeg-turbo-1.2.1.tar.gz ./configure –help ./configure --prefix=/work/proj ...

  7. Day4_装饰器

    装饰器: #模板def auth(func): def wrapper(*args,**kwargs): res=func(*args,**kwargs) return res return wrap ...

  8. MVC动态绑定下拉框

    Controller: //获取下拉信息表 //_vendorsAppService.GetAllObj() 是获取下拉列表结果集 ViewData["vendlist"] = n ...

  9. UOJ#349. 【WC2018】即时战略

    原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ349.html 题解 被cqz D没了.我D cly 关你啥事(逃 首先链的情况直接rand就好了. 期望 ...

  10. 微软官网tools

    DHCP/AD域插件: 远程管理工具(含DHCP/AD域) 安装网址: https://www.microsoft.com/zh-cn/download/details.aspx?id=7887 程序 ...