文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡(jiǎn)書(shū)

1. Description

Copy List with Random Pointer

2. Solution

• Version 1

/**
 * 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) {
        if(!head) {
            return nullptr;
        }
        vector<RandomListNode*> origin;
        vector<RandomListNode*> target;
        RandomListNode* result = new RandomListNode(head->label);
        origin.push_back(head);
        target.push_back(result);
        RandomListNode* prev = result;
        RandomListNode* current = head->next;
        while(current) {
            RandomListNode* node = new RandomListNode(current->label);
            prev->next = node;
            prev = node;
            origin.push_back(current);
            target.push_back(node);
            current = current->next;
        }
        for(int i = 0; i < origin.size(); i++) {
            if(!origin[i]->random) {
                continue;
            }
            for(int j = 0; j < origin.size(); j++) {
                if(origin[i]->random == origin[j]) {
                    target[i]->random = target[j];
                    break;
                }
            }
        }
        return result;
    }
};

• Version 2

/**
 * 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) {
        if(!head) {
            return nullptr;
        }
        unordered_map<RandomListNode*, RandomListNode*> correspond;
        RandomListNode* result = new RandomListNode(head->label);
        RandomListNode* prev = result;
        RandomListNode* current = head->next;
        correspond[head] = result;
        while(current) {
            RandomListNode* node = new RandomListNode(current->label);
            prev->next = node;
            prev = node;
            correspond[current] = node;
            current = current->next;
        }
        RandomListNode* copy_current = result;
        current = head;
        while(current) {
            copy_current->random = correspond[current->random];
            current = current->next;
            copy_current = copy_current->next;
        }
        return result;
    }
};

• Version 3

/**
 * 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) {
        if(!head) {
            return nullptr;
        }
        RandomListNode* current = head;
        while(current) {
            RandomListNode* node = new RandomListNode(current->label);
            node->next = current->next;
            current->next = node;
            current = current->next->next;
        }
        current = head;
        while(current) {
            if(current->random) {
                current->next->random = current->random->next;
            }
            current = current->next->next;
        }
        RandomListNode* result = head->next;
        RandomListNode* copy_current = head->next;
        current = head;
        while(current) {
            current->next = current->next->next;
            if(copy_current->next) {
                copy_current->next = copy_current->next->next;
            }
            else {
                copy_current->next = nullptr;
            }
            current = current->next;
            copy_current = copy_current->next;
        }
        return result;
    }
};

Reference

1. https://leetcode.com/problems/copy-list-with-random-pointer/description/