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.
We can copy each nodes first and make the copied node connected to the old one. And then it is easier to copy the random pointer by node.next.random = node.random.next because each node, its next node is its copied node.
C++ Code:
/*
* func: copy_list_with_random_pointer
* goal: deep copy a list with random pointer
* @param head: head node of the list
* return: new head node of the list
*/
RandomListNode *copy_list_with_random_pointer(RandomListNode *head){
if(head == nullptr){
return nullptr;
}
RandomListNode *iter = head;
//Copy the list sequentially first
//t1->t1_cpy->t2->t2_cpy->NULL
while(iter != nullptr){
//Get current node's next first
RandomListNode *next = iter->next;
//Copy current node
iter->next = new RandomListNode(iter->label);
//Connect copied node to the next node
iter->next->next = next;
//Go to the next node
iter = next;
}
iter = head;
while(iter != nullptr){
//Get current node's next node first
RandomListNode *next = iter->next->next;
//Copy random pointer
iter->next->random = iter->random == nullptr ? nullptr : iter->random->next;
//Go to the next node
iter = next;
}
//Set the new head
RandomListNode *new_head = head->next;
iter = head;
while(iter != nullptr){
RandomListNode *next = iter->next->next;
//Connect the current node's next to the next node's copy node
iter->next->next = next == nullptr ? nullptr : next->next;
//Re-connect current node to its original next node
iter->next = next;
//Go to the next node
iter = next;
}
return new_head;
}
Python Code:
# func: copy linked list with random pointers
# @param head: head node of the list
# @return: new head node
def copy_random_list(head):
if not head:
return None
#Copy nodes first
curr = head
while curr:
next_node = curr.next
curr.next = RandomListNode(curr.label)
curr.next.next = next_node
curr = next_node
#Copy random pointer
curr = head
while curr:
next_node = curr.next.next
curr.next.random = curr.random.next if curr.random else None
curr = next_node
#Split two lists
new_head = head.next
curr = head
while curr:
next_node = curr.next.next
curr.next.next = next_node.next if next_node else None
curr.next = next_node
curr = next_node
return new_head
