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.
Solution1:Two pass(copy + random) Hashmap
思路:
(1)先處理元素本值復(fù)制部分: 遍歷原list(nodes_src),對應(yīng)建立(復(fù)制)一個新的list(nodes_copy)策治,節(jié)點分別復(fù)制管宵;
遍歷過程中,建立一個map(node_src -> node_copy)赂韵,用來后續(xù)處理random
(2)random部分的復(fù)制: 同步遍歷list_src 和 list_copy, node_copy的random為 其(node_copy)對應(yīng)的node_src的random對應(yīng)(src->映射map->copy)的node_copy
實現(xiàn)1a: 建立新list的時候直接先連起來,更快些
(實現(xiàn)1b: 不先連,在第二次遍歷的時候通過get(node_src->node_copy)來找node_copy再連接宏娄,代碼看起來簡潔毙石,但速度慢)
Time Complexity: O(N) Space Complexity: O(N)
Solution2:依次在旁邊復(fù)制 連好random 再剝離
思路:Solution1中用hashmap是為了解決random時的node_src->node_copy的對應(yīng)問題廉沮,是因為否則在遍歷后我們無法訪問到該copy中的random結(jié)點。
方法二先將node_copy在原list中復(fù)制徐矩,-> src -> [copy] -> src -> [copy] -> src -> [copy] -> ...滞时,
這樣一來在遍歷的過程中,因為node_copy和node_src在同一list中滤灯,node_copy(即cur_src.next).random 就是cur_src.random.next(找到random對應(yīng)的copy結(jié)點);
最后再extract the copy list 即可
Time Complexity: O(N) Space Complexity: O(1)
Solution1a Code:
public class Solution {
public RandomListNode copyRandomList(RandomListNode src_head) {
if(src_head == null) return null;
HashMap<RandomListNode, RandomListNode> node_map = new HashMap<>();
// first traversal
// (1)build a new node list by deeply copying from node_src
// (2)build node_map mapping node_src -> node_copy for every node_src
RandomListNode dummy_copy = new RandomListNode(0);
RandomListNode cur_src = src_head;
RandomListNode prev_copy = dummy_copy;
while(cur_src != null) {
RandomListNode node_copy = new RandomListNode(cur_src.label);
prev_copy.next = node_copy;
node_map.put(cur_src, node_copy);
cur_src = cur_src.next;
prev_copy = node_copy;
}
// second traversal
// to add random ptr for each node_copy, by checking the map about which node_copy
// (by corresponding node_src random relationship) that every node_copy.random should points to
cur_src = src_head;
RandomListNode cur_copy = dummy_copy.next;
while(cur_src != null) {
cur_copy.random = node_map.get(cur_src.random);
cur_src = cur_src.next;
cur_copy = cur_copy.next;
}
return dummy_copy.next;
}
}
Solution1b Code:
public class Solution {
public RandomListNode copyRandomList(RandomListNode src_head) {
if(src_head == null) return null;
HashMap<RandomListNode, RandomListNode> node_map = new HashMap<>();
// first traversal
// build node_map mapping node_src -> node_copy for every node_src
RandomListNode cur_src = src_head;
while(cur_src != null) {
RandomListNode node_copy = new RandomListNode(cur_src.label);
node_map.put(cur_src, node_copy);
cur_src = cur_src.next;
}
// second traversal
// to add random ptr for each node_copy, by checking the map about which node_copy; and to link copy_nodes also by getting from map
// (by corresponding node_src random relationship) that every node_copy.random should points to
cur_src = src_head;
while(cur_src != null) {
node_map.get(cur_src).next = node_map.get(cur_src.next);
node_map.get(cur_src).random = node_map.get(cur_src.random);
cur_src = cur_src.next;
}
return node_map.get(src_head);
}
}
Solution2 Code:
public class Solution {
public RandomListNode copyRandomList(RandomListNode src_head) {
if(src_head == null) return null;
// First traversal: Make copy of each node
// -> src -> [copy] -> src -> [copy] -> src -> [copy] -> ...
RandomListNode cur_src = src_head;
RandomListNode cur_src_next_save;
while(cur_src != null) {
cur_src_next_save = cur_src.next;
RandomListNode node_copy = new RandomListNode(cur_src.label);
cur_src.next = node_copy;
node_copy.next = cur_src_next_save;
cur_src = cur_src_next_save;
}
// Second traversal: assign random pointers for the copy nodes
cur_src = src_head;
while(cur_src != null) {
if(cur_src.random != null) {
cur_src.next.random = cur_src.random.next;
}
cur_src = cur_src.next.next;
}
// Third traversal: restore the original list, and extract the copy list.
cur_src = src_head;
RandomListNode dummy_copy = new RandomListNode(0);
RandomListNode cur_copy = dummy_copy;
while(cur_src != null) {
// extract the copy
cur_copy.next = cur_src.next;
cur_copy = cur_copy.next;
// restore the original list
cur_src.next = cur_src.next.next;
cur_src = cur_src.next;
}
return dummy_copy.next;
}
}