# My C++ solution (115ms, O(n) time, O(1) space)

• The algorithm needs to scan the list three time, one to copy nodes, one to copy random fields, and the last to reconnect the original list and the new list. The basic idea is to interleave the original list and the new list to facilitate the random field copy. "Interleave" means "old_node1->new_node1->old_node2->new_node_2->..."

class Solution {
public:

``````        if(!head)
{
return NULL;
}
else
{
// generate a new list and interleave it with the original list
while(p1)
{
p2 = new RandomListNode(p1->label);
temp = p1->next;
p1->next = p2;
p2->next = temp;
p1 = temp;
}

// copy the random fields of the new list
while(p1)
{
p2 = p1->random;
if(p2)
{
p1->next->random = p2->next;
}
p1 = p1->next->next;
}

// separate the original and new lists
while(p2->next)
{
p1->next = p2->next;
p1= p1->next;
p2->next = p1->next;
p2 = p2->next;
}
p1->next = NULL;
}
}
};``````

• This post is deleted!

• I don't know why this solution cost O(1) space.
Won't the newnode cost O(n) space?

• I think it means O(1) EXTRA space to copy random pointers.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.