My O(n) time O(1) space cpp code without using hash


  • 0
    C
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head)
        {
            RandomListNode* ptr = head;
            while(ptr)
            {
                RandomListNode* newNode = new RandomListNode(ptr->label);
                newNode->random = ptr->random;
                
                newNode->next = ptr->next;
                ptr->next = newNode;
                ptr = ptr->next->next;
            }
            
            ptr = head;
            while(ptr)
            {
                ptr = ptr->next;
                if(ptr->random) ptr->random = ptr->random->next;
                ptr = ptr->next;
            }
            
            RandomListNode originFake(0), newFake(0);
            RandomListNode* originPtr = &originFake, *newPtr = &newFake;
            
            ptr = head;
            while(ptr)
            {
                originPtr->next = ptr;
                originPtr = originPtr->next;
                
                newPtr->next = ptr->next;
                newPtr = newPtr->next;
                
                ptr = ptr->next->next;
            }
            
            originPtr->next = NULL;
            newPtr->next = NULL;
            
            return newFake.next;
        }
    };

Log in to reply
 

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