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


  • -6
    N

    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;
    	}
    };

  • 0
    C

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


  • 0
    E
    This post is deleted!

  • 0
    N

    the arr of size N is the result, the final duplicate list node.
    Please read my code.


  • 0
    N

    why is it O(1) space complexity?


  • 0
    Y

    I agree that it's O(1) space complexity, but you are leveraging the continuous characteristic of array in the copying, so your copied link list is not a real link list.


  • 0
    J

    Are you sure the OJ can safely free the whole list?


Log in to reply
 

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