A C++ solution beats 99.35% solutions with explanations


  • 2
    L
    class Solution {
    public:
        /***************************************************
         *  1----->2------->3-------->4
         *  ↓             ↗ ↑|       
         *  |-----------/---||       
         *            /      |
         *          /        |
         *  |-----/---------||
         *  |   /           ↓↓
         *  1------>2------->3------->4
        ***************************************************/
        RandomListNode *copyRandomList(RandomListNode *head) {
            RandomListNode *newHead;
            RandomListNode *current1=head, *current2, *runner1, *runner2;
            vector<RandomListNode*> tmp;            // To store original list random points and recover later
            int i=0;
            
            if(!head) return NULL;
            
            newHead = new RandomListNode(head->label);
            newHead->random = head->random;
            tmp.push_back(head->random);
            
            head->random = newHead;                 // Make the original head random point to the new head
            
            current2 = newHead;
            current1 = head->next;
            
            while(current1){
                RandomListNode *newNode = new RandomListNode(current1->label);
                current2->next = newNode;
                newNode->random = current1->random;         // The new list random point points at the next original list random node
                
                tmp.push_back(current1->random);            // Store the random node of current original list node
                current1->random = newNode;                 // The original list random point points at the new list corresponding node
                
                current2 = newNode;
                current1 = current1->next;
            }
            
            current2 = newHead;
            while(current2){    
                if(current2->random)                            // To make the new list node random node points at the corresponding node of
                                                                // the ones in the original node
                    current2->random = current2->random->random;
                else
                    current2->random = NULL;
                current2 = current2->next;
            }
            
            current1 = head;
            while(current1){                                    // Restore the original list with information stored
                current1->random = tmp[i++];
                current1 = current1->next;
            }
            return newHead;
        }
    };
    

Log in to reply
 

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