# A new method of O(n) time and O(1) space

1. allocate all the memory for the copy of list, the list is actually
an array where the next point of result[i] is &result[i+1]

2. Initialize the copy of list. The next pointer of copy point to its
original node, and the next of original pointing to the copy
therefore we have two way map

3. Using the two way map to find the correct random of copy

4. restore the modified next of original list, and the copy list

class Solution {
public:
int len = 0;
for (RandomListNode iter=head; iter; iter=iter->next) len++;
if (len==0)
return NULL;
RandomListNode
result = reinterpret_cast<RandomListNode
>(new char[len
sizeof(RandomListNode)]);
for (int i=0; iter; i++) {
result[i].label = iter->label;
result[i].next = iter;
RandomListNode *next = iter->next;
iter->next = result+i;
iter = next;
}
for (int i=0; i<len; i++) {
if (result[i].next->random)
result[i].random = result[i].next->random->next;
else
result[i].random = NULL;
}
for (int i=0; i<len-1; i++) {
result[i].next->next = result[i+1].next;
result[i].next = result+i+1;
}
result[len-1].next->next = NULL;
result[len-1].next = NULL;
return result;
}
};

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