C++ solution with O(n) time &O(1) space complexity for your reference


  • 2
    H

    At first, I think the connection between the old link list and the new one could be recorded using a hash table, which leads to a space complexity of O(n). The solution below only uses O(1) space.

    Here is the thought:

    Step 1. Copy and insert the node after every node in the original link list;

    Step 2. Build up the random connections among the new nodes.

    Step 3. Divide the two link list and make the new one independent.

    class Solution {
    public:
    	RandomListNode *copyRandomList(RandomListNode *head) {
    		CopyNodes(head);
    		ConnectRandomNodes(head);
    		return ReconnectNodes(head);
    	}
    private:
    	//Copy a node after every node in the original linklist;
    	void CopyNodes(RandomListNode *head)
    	{
    		RandomListNode* node = head;
    		while (node){
    			RandomListNode* copy = new RandomListNode(0);
    			copy->label = node->label;
    			copy->next = node->next;
    			copy->random = NULL;
    			node->next = copy;
    			node = copy->next;
    		}
    	}
    	//copy the random link in the original linklist;
    	void ConnectRandomNodes(RandomListNode *head)
    	{
    		RandomListNode *node = head;
    		while (node){
    			RandomListNode *copy = node->next;
    			if(node->random) 
    				copy->random = node->random->next;
    			node = copy->next;
    		}
    	}
    	//divide the linklist to two linklists
    	RandomListNode *ReconnectNodes(RandomListNode *head)
    	{
    		RandomListNode *CopyHead = NULL, *copy = NULL;
    		RandomListNode *node = head;
    		if (node){
    			CopyHead = node->next;
    			copy = node->next;
    			node->next = copy->next;
    			node = node->next;
    		}
    		while (node){
    			copy->next = node->next;
    			copy = copy->next;
    			node->next = copy->next;
    			node = node->next;
    		}
    		return CopyHead;
    	}
    };

Log in to reply
 

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