IS there any faster method?


  • 11
    N

    I solve this problem by costing 392ms.
    I use map to save the relation between the original list and the copy one.


  • 0
    S

    That's about the only way you could keep track of the vertices that were processed. So there is no faster method.


  • 6
    S

    Mine takes 572ms. How could I improve this?
    I'm using same idea to keep track of copied nodes with hashmap.

    public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode,RandomListNode> nodemap = new HashMap<RandomListNode,RandomListNode>();
        return copyListHelper(head, nodemap);
    }
    public RandomListNode copyListHelper(RandomListNode head, HashMap<RandomListNode,RandomListNode> nodemap)  {
        if(head==null)  return null;
        if(nodemap.containsKey(head))  return nodemap.get(head);
        RandomListNode ret = new RandomListNode(head.label);
        nodemap.put(head,ret);
        ret.next = copyListHelper(head.next, nodemap);
        ret.random = copyListHelper(head.random,nodemap);
        return ret;
    }
    

    }


  • 0
    Y

    Mine is 352 ms, but probably takes more space than you do.

    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            unordered_map<int, int> indexMap;
            unordered_map<int, int> randomMap;
            vector<RandomListNode*> randomList;
            int i = 0;
            RandomListNode* victim = head;
            RandomListNode* result = new RandomListNode(0);
            RandomListNode* resultVictim = result;
            
            while(victim != NULL) {
                indexMap[(int)victim] = i;
                i++;
                victim = victim->next;
            }
            
            i = 0;
            victim = head;
            while(victim != NULL) {
                if(victim->random != NULL) {
                    randomMap[i] = indexMap[(int)victim->random];
                }
                resultVictim->next = new RandomListNode(victim->label);
                resultVictim = resultVictim->next;
                randomList.push_back(resultVictim);
                i++;
                victim = victim->next;
            }
            
            while(--i >= 0) {
                if(randomMap.find(i) != randomMap.end())
                    randomList[i]->random = randomList[randomMap[i]];
            } 
            
            return result->next;
        }
    };

  • 1
    S

    When you are sharing your solution, please add words about your algorithm, and make some comment in your code. Thanks.


  • 5
    Z

    My algorithm spend 292ms~308ms(changed each time, maybe according to the state of server).

    1. copy the list with random pointer stay null and assign the label of all the listnode in the original equal to its index inthe list.
    2. allocate an array of RandomListNode* with same size as the list.
    3. Copy the linknode address into the array. and we can use label of original list as index of the array.
    4. Recover the label in ori version using the copy version.

    Since i do not use map, time complexity should be linear.

    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL)
            return NULL;
        int i, len = 1;
        RandomListNode *p = head->next, **r_pointer, *r_head = NULL, *r_tail = NULL;
        
        r_head = new RandomListNode(head->label);
        r_tail = r_head;
        head->label = 0;
        
        while(p != NULL){
            r_tail->next = new RandomListNode(p->label);
            r_tail = r_tail->next;
            p->label = len;
            p = p->next;
            len ++;
        }
        r_pointer = new RandomListNode* [len];
        r_tail = r_head;
        i = 0;
        while(r_tail != NULL){
            r_pointer[i] = r_tail;
            i++;
            r_tail = r_tail -> next;
        }
        r_tail = r_head;
        p = head;
        while(p != NULL){
            RandomListNode *tmp = p->random;
            if(tmp != NULL){
                r_tail->random = r_pointer[tmp->label];
            }
            p = p->next;
            r_tail = r_tail->next;
        }
        r_tail = r_head;
        p = head;
        while(p != NULL){
            p->label = r_tail->label;
            p = p->next;
            r_tail = r_tail->next;
        }
        return r_head;
    }

  • 108
    P

    Mine is 276 ms. O(n) time complexity and O(1) space complexity.

        RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL) return NULL;
        RandomListNode *p = head;
        do {
            RandomListNode *q = p->next;
            p->next = new RandomListNode(p->label);
            p->next->next = q;
            p = q;
        } while(p != NULL);
        p = head;
        do {
            p->next->random = (p->random == NULL) ? NULL : p->random->next;
            p = p->next->next;
        } while(p != NULL);
        p = head;
        RandomListNode *r = head->next;
        for(RandomListNode *q = r;;) {
            p->next = q->next;
            p = p->next;
            if(p == NULL) break;
            q->next = p->next;
            q = q->next;
        }
        return r;
    }

  • 0
    H

    put the nodes in the original linked list to keep track of the order, smart!


  • 0
    S

    your using Java, maybe thats the reason. It is slightly slower


  • 0
    M

    excellent answer thx very much :)


  • 0
    C
    Mine is 280 ms. O(1) space complexity. A little tricky, store the each RandomListNode address diff between head and newHead in the label.
    
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL) return NULL;
        RandomListNode *newHead = new RandomListNode(head->label);
        newHead->random = head->random;
        head->label = newHead - head;
        
        RandomListNode *p = head->next, *q = newHead, *t;
        while(p) {
            t = new RandomListNode(p->label);
            t->random = p->random;
            p->label = t - p;
            q->next = t;
            q = t;
            p = p->next;
        }
        
        q = newHead;
        while(q) {
            if(q->random)
                q->random = q->random + q->random->label;
            q = q->next;
        }
        
        p = head;
        q = newHead;
        while(p) {
            p->label = q->label;
            p = p->next;
            q = q->next;
        }
        return newHead;
    }

  • 0
    M

    I used a map. I'll see if I can post it. I tried as a comment and it was a mess.


  • 0
    M

    Here is what I did, I was able to get down into the 320ms range:

    /**
     * Definition for singly-linked list with a random pointer.
     * struct RandomListNode {
     *     int label;
     *     RandomListNode *next, *random;
     *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
     * };
     */
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            // slightly faster with unordered_map (hash table) vs map (tree)
            unordered_map<RandomListNode *,RandomListNode *> oldToNewMap;
            RandomListNode *newHead = NULL;
            if(!head) {
                return NULL;
            }
            RandomListNode * currentOldNode = head;
            RandomListNode * currentNewNode = NULL;
            while(currentOldNode) {
    // more correct/idiomatic, but slower
    //            if(oldToNewMap.find(currentOldNode) == oldToNewMap.end()) {
    //                oldToNewMap[currentOldNode] = new RandomListNode(currentOldNode->label);
    //            } 
    
    // faster, but not fast enough
    //            if(oldToNewMap[currentOldNode] == NULL) {
    //                oldToNewMap[currentOldNode] = new RandomListNode(currentOldNode->label);
    //            } 
    //            currentNewNode = oldToNewMap[currentOldNode];
    
    
                // cache the map location with a reference for fastest yet
                RandomListNode*& t1 = oldToNewMap[currentOldNode];
                if(t1 == NULL) {
                    t1 = new RandomListNode(currentOldNode->label);
                } 
                currentNewNode = t1;
    
                if(currentOldNode->next) {
    // more correct/idiomatic, but slower
    //                if(oldToNewMap.find(currentOldNode->next)==oldToNewMap.end()) {
    //                    oldToNewMap[currentOldNode->next] = new RandomListNode(currentOldNode->next->label);
    //                }
    
    // faster, but not fast enough
    //                if(oldToNewMap[currentOldNode->next] == NULL) {
    //                  oldToNewMap[currentOldNode->next] = new RandomListNode(currentOldNode->next->label);
    //              }
    //              currentNewNode->next = oldToNewMap[currentOldNode->next];
    
                    // cache the map location with a reference for fastest yet
                    RandomListNode*& t2 = oldToNewMap[currentOldNode->next];
                    if(t2 == NULL) {
                        t2 = new RandomListNode(currentOldNode->next->label);
                    }
                    currentNewNode->next = t2;
    
                }
                if(currentOldNode->random) {
    // more correct/idiomatic, but slower
    //                if(oldToNewMap.find(currentOldNode->random)==oldToNewMap.end()) {
    //                    oldToNewMap[currentOldNode->random] = new RandomListNode(currentOldNode->random->label);
    //                }
    
    // faster, but not fast enough
    //              if(oldToNewMap[currentOldNode->random] == NULL) {
    //                  oldToNewMap[currentOldNode->random] = new RandomListNode(currentOldNode->random->label);
    //              }
    //              currentNewNode->random = oldToNewMap[currentOldNode->random];
                    
                    // cache the map location with a reference for fastest yet
                    RandomListNode*& t3 = oldToNewMap[currentOldNode->random];
                    if(t3 == NULL) {
                        t3 = new RandomListNode(currentOldNode->random->label);
                    }
                    currentNewNode->random = t3;
                }
                currentOldNode = currentOldNode->next;
            }
            return oldToNewMap[head];
        }
    };
    

  • 0
    S

    FWIW: some writeup to explain the algorithm above

    1. the first loop inserts newly copied node into the original linked list right after the node being copied. E.g., originally (node 0) -> (node 1) -> ...; after the loop, it becomes (node 0) -> (node 0 copy) -> (node 1) -> (node 1 copy) -> ...
    2. after the first loop, we know random pointers (p^) for the copied nodes (n^) should point to the immediate following nodes of those (p) being pointed by the nodes being copied (n). take the example above, if the random pointer of (node 0) points at (node 1), then the random pointer of (node 0 copy) points at the immediate following node of (node 1), namely (node 1 copy). this is what the second loop does
    3. collect copied nodes and reset the original list back

  • 0
    P

    Excellent explanation! It's exactly what I meant.


  • 0
    D
    This post is deleted!

  • 0
    D

    244ms using an unordered map and just two loops. One to copy the list and the second to set the random address.


  • 0
    H

    This is awesome!


  • 0
    C

    brilliant solution!


  • 2
    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.

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

Log in to reply
 

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