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.

---

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