Leetcode 138. Copy List with Random Pointer | | Leetcode 138. Copy List with Random Pointer 文章作者:Tyan博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 12345678910111213141516171819202122232425262728293031323334353637383940414243/** * 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<RandomListNode*> origin; vector<RandomListNode*> 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 123456789101112131415161718192021222324252627282930313233343536/** * 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<RandomListNode*, RandomListNode*> 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 123456789101112131415161718192021222324252627282930313233343536373839404142434445/** * 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/ 如果有收获,可以请我喝杯咖啡! 赏 微信打赏 支付宝打赏