【Algorithm|Leetcode 138. Copy List with Random Pointer】文章作者：Tyan
博客：noahsnail.com|CSDN|简书
1. Description 
文章图片
2. Solution
- Version 1
/**
* 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) {
if(!head) {
return nullptr;
}
vector origin;
vector target;
RandomListNode* result = new RandomListNode(head->label);
origin.push_back(head);
target.push_back(result);
RandomListNode* prev = result;
RandomListNode* current = head->next;
while(current) {
RandomListNode* node = new RandomListNode(current->label);
prev->next = node;
prev = node;
origin.push_back(current);
target.push_back(node);
current = current->next;
}
for(int i = 0;
i < origin.size();
i++) {
if(!origin[i]->random) {
continue;
}
for(int j = 0;
j < origin.size();
j++) {
if(origin[i]->random == origin[j]) {
target[i]->random = target[j];
break;
}
}
}
return result;
}
};
- Version 2
/**
* 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) {
if(!head) {
return nullptr;
}
unordered_map correspond;
RandomListNode* result = new RandomListNode(head->label);
RandomListNode* prev = result;
RandomListNode* current = head->next;
correspond[head] = result;
while(current) {
RandomListNode* node = new RandomListNode(current->label);
prev->next = node;
prev = node;
correspond[current] = node;
current = current->next;
}
RandomListNode* copy_current = result;
current = head;
while(current) {
copy_current->random = correspond[current->random];
current = current->next;
copy_current = copy_current->next;
}
return result;
}
};
- Version 3
/**
* 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) {
if(!head) {
return nullptr;
}
RandomListNode* current = head;
while(current) {
RandomListNode* node = new RandomListNode(current->label);
node->next = current->next;
current->next = node;
current = current->next->next;
}
current = head;
while(current) {
if(current->random) {
current->next->random = current->random->next;
}
current = current->next->next;
}
RandomListNode* result = head->next;
RandomListNode* copy_current = head->next;
current = head;
while(current) {
current->next = current->next->next;
if(copy_current->next) {
copy_current->next = copy_current->next->next;
}
else {
copy_current->next = nullptr;
}
current = current->next;
copy_current = copy_current->next;
}
return result;
}
};
Reference
- https://leetcode.com/problems/copy-list-with-random-pointer/description/
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- Python - Search Insert Position
- LeetCode 28 Implement strStr() (C,C++,Java,Python)