C++ O(n) time and O(1) space


#1
RandomListNode* Solution::copyRandomList(RandomListNode* head) 
{
    if(!head)
        return NULL;
    for(auto node = head; node; )
    {
        auto newNode = new RandomListNode(node -> label);
        auto next = node -> next;
        node -> next = newNode;
        newNode -> next = next;
        node = next;
    }
    for(auto node = head; node and node -> next; node = node -> next -> next)
        if(node -> random)
            node -> next -> random = node -> random -> next;
    for(auto node = head -> next; node and node -> next; node = node -> next)
        node -> next = node -> next -> next;
    return head -> next;
}

#2

Nice code. I am adding solution details for those who could not understand the above code.
The first for loop is adding new node in between the original nodes. So after first loop link list will look like this : 1->1->2->2->3->3
In second loop, random pointers of new nodes are set.
In third loop, original nodes are removed from the link list by changing pointer of new nodes to their respective new nodes. So link list look like this : 1->1->2->3 and the head next is returned.


#3

You are creating duplicates nodes ,so space complexity should be O(n)