A solution which will change original link list, but simple


  • -1
    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 = copyHead;
        struct RandomListNode* prevCopyNode = NULL;
        
    
        // copy original linklist at first, even the random pointer
        // then change original list's next pointer to its relative copied node
        // so copyNode->random = copyNode->random->next
        while(orgNode != NULL) {
            copyNode = (struct RandomListNode*)malloc(sizeof(struct RandomListNode));
            if(copyNode != NULL) {
                copyNode->label = orgNode->label;
                copyNode->random = orgNode->random;
                copyNode->next = NULL;
                if(prevCopyNode == NULL) {
                    copyHead = copyNode;
                }
                else {
                    prevCopyNode->next = copyNode;
                }
                prevCopyNode = copyNode;
                
                //change original link list's next pointer to its relative copy list list node
                struct RandomListNode* prevOrgNode = orgNode;
                orgNode = orgNode->next;
                prevOrgNode->next = copyNode;
            } 
            else {
                break;
            }
        }
        
        copyNode = copyHead;
        while(copyNode != NULL) {
            if(copyNode->random != NULL) {
                copyNode->random = copyNode->random->next;
            }
            
            copyNode = copyNode->next;
        }
        
        return copyHead;
    }

Log in to reply
 

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