首页 > 代码库 > LeetCode: Copy List with Random Pointer
LeetCode: Copy List with Random Pointer
LeetCode: Copy List with Random Pointer
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.
地址：https://oj.leetcode.com/problems/copy-list-with-random-pointer/
算法：将已经复制的节点存储在map里面。如果当前遍历到的节点在map里，则直接取出来；若不再map里则复制节点，并将节点存储在map里。代码:
1 /** 2 * Definition for singly-linked list with a random pointer. 3 * struct RandomListNode { 4 * int label; 5 * RandomListNode *next, *random; 6 * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 RandomListNode *copyRandomList(RandomListNode *head) {12 RandomListNode *p = head;13 RandomListNode *new_head = NULL;14 map<int, RandomListNode*> hash_table;15 RandomListNode *new_p;16 int label, r_label;17 while(p){18 label = p->label;19 if(hash_table.find(label) == hash_table.end()){20 RandomListNode * temp_p = new RandomListNode(label);21 hash_table[label] = temp_p;22 }23 if(!new_head){24 new_head = hash_table[label];25 new_p = new_head;26 }else{27 new_p->next = hash_table[label];28 new_p = new_p->next;29 }30 if(p->random){31 r_label = p->random->label;32 if(hash_table.find(r_label) == hash_table.end()){33 RandomListNode *temp_p = new RandomListNode(r_label);34 hash_table[r_label] = temp_p;35 }36 new_p->random = hash_table[r_label];37 }38 p = p->next;39 }40 return new_head;41 }42 };
LeetCode: Copy List with Random Pointer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。