My solution is 268ms~276 ms. And O(n) time complexity with O(1) space complexity.

Make good use of the characteristic of Array.

And Array is more cache-friendly than List.

So I think some operations in loop can be sped up by this advantage.

(I know that there is a smart approach that put the nodes in the original linked list to keep track of the order. But hope to provide a different way.)

```
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head)
{
if (head == NULL) return NULL;
int size = 0, i = 0;
RandomListNode *now = head, *next, *tmp;
while (now != NULL)
{
size++;
now = now->next;
}
RandomListNode *arr = (RandomListNode*) malloc(size * sizeof(RandomListNode));
// Copy the list
now = head;
while (now != NULL)
{
memcpy(arr + i, now, sizeof(RandomListNode));
next = now->next;
// Let the original listNode->next point to the duplicate listNode
now->next = arr + i;
i++;
now = next;
}
// Handle the pointer random of duplicate listNode
for (i = 0; i < size; i++)
{
tmp = arr + i;
if (tmp->random != NULL)
{
tmp->random = tmp->random->next;
}
}
// Recover the pointer next of original listNode
now = head;
for (i = 0; i < size; i++)
{
tmp = arr + i;
now->next = tmp->next;
now = now->next;
}
// Use the characteristic of array to store the pointer next of duplicate listNode
for (i = 0; i < size; i++)
{
tmp = arr + i;
tmp->next = tmp + 1;
}
arr[size - 1].next = NULL;
return arr;
}
};
```