# Here is my solution, cost 268ms, O(n) time complexity and O(1) space complexity.

• 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:
{
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
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
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;
}
};``````

• how do you call this O(1) space complexity when you're creating a arr of size N??

• This post is deleted!

• the arr of size N is the result, the final duplicate list node.