With error "Random pointer of node with label -1 points to a node from the original list.", can anyone help me?


  • 5
    T
    /**
     * 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) {
    		vector<RandomListNode *> vecOld;
    		unordered_map<RandomListNode *, size_t> addressIndexMap;
    		vector<RandomListNode *> vecAddress;
    		if (!head)
    		{
    			return NULL;
    		}
    		else if (!head->next)
    		{
    			return new RandomListNode(*head);
    		}
    		RandomListNode * curr = head;
    		RandomListNode * guard = new RandomListNode(0);
    		RandomListNode * newCurr = guard;
    		while (curr)
    		{
    		    //store the old random pointer 
    			vecOld.push_back(curr->random);
    			//store the old address -> index pair for later reconstruction of random pointer
    			addressIndexMap[curr] = vecOld.size() - 1;
    			newCurr->next = new RandomListNode(*curr);
    			newCurr = newCurr->next;
    			newCurr->random = NULL;
    			//store the address of new nodes for later reconstruction of random pointer
    			vecAddress.push_back(newCurr);
    			curr = curr->next;
    		}
    		newCurr = guard->next;
    		int index = 0;
    		while (newCurr)
    		{
    		    //If the old random pointer is not NULL
    			if (NULL != vecOld[index])
    			{
    			    //Get the corresponding index
    				size_t randomIndex = addressIndexMap[vecOld[index]];
    				//get the new address of the node with the index and reconstruct the random pointer
    				newCurr->random = vecAddress[randomIndex];
    			}
    			++index;
    			newCurr = newCurr->next;
    		}
    		newCurr = guard->next;
    		delete guard;
    		return newCurr;
    	}
    };

  • 0
    S

    what's the problem? can you point it out explicitly? Thanks.


Log in to reply
 

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