My 28ms simple C solution with O(n) time and O(1) space


  • 2
    H
    /**
     * Definition for singly-linked list with a random pointer.
     * struct RandomListNode {
     *     int label;
     *     struct RandomListNode *next;
     *     struct RandomListNode *random;
     * };
     */
    struct RandomListNode *copyRandomList(struct RandomListNode *head) {
        struct RandomListNode* copyHead = NULL;
        struct RandomListNode* orgNode = head;
        struct RandomListNode* copyNode = NULL;
        struct RandomListNode* prevCopyNode = NULL;
        
        if(head == NULL) {
            return NULL;
        }
        
        //insert copied linklist into orginal link list
        while(orgNode != NULL) {
            copyNode = (struct RandomListNode*)malloc(sizeof(struct RandomListNode));
            if(copyNode != NULL) {
                copyNode->next = orgNode->next;
                copyNode->label = orgNode->label;
                orgNode->next = copyNode;
                orgNode = orgNode->next->next;
            }
            else {
                break;
            }
        }
        
        //assign random pointer for copied nodes
        orgNode = head;
        while(orgNode != NULL) {
            if(orgNode->random != NULL) {
                orgNode->next->random = orgNode->random->next;
            }
            else {
                orgNode->next->random = NULL;
            }
            
            orgNode = orgNode->next->next;
        }
        
        //split 2 link lists
        copyHead = head->next;
        orgNode = head;
        while(orgNode != NULL) {
            copyNode = orgNode->next;
            
            orgNode->next = copyNode->next;
            if(prevCopyNode != NULL) {
                prevCopyNode->next = copyNode;
            }
            prevCopyNode = copyNode;
            orgNode = copyNode->next;
        }
        
        return copyHead;
    }

  • 0
    Z

    Very smart, thanks!


Log in to reply
 

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