Solution

• 利用map保存节点信息

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
// 用map保留过曾经访问过的值
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if (pHead == nullptr) return nullptr;
        
        unordered_map<RandomListNode*, RandomListNode*> nodeMap;
        for (auto *cur = pHead; cur != nullptr; cur = cur->next) {
            nodeMap[cur] = new RandomListNode(cur->label);
        }
        
        for (auto *cur = pHead; cur != nullptr; cur = cur->next) {
            nodeMap[cur]->next = nodeMap[cur->next];
            nodeMap[cur]->random = nodeMap[cur->random];
        }
        return nodeMap[pHead];
    }
};

• 复制、重排、拆分

*1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
*2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
*3、拆分链表，将链表拆分为原链表和复制后的链表

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if (pHead == nullptr) return nullptr;
        RandomListNode *cur = pHead;
        while (cur) {
            RandomListNode *node = new RandomListNode(cur->label);
            node->next = cur->next;
            cur->next= node;
            cur = node->next;
        }
        
        RandomListNode *cur1 = pHead, *cur2;
        while (cur1) {
            cur2 = cur1->next;
            if (cur1->random)
                cur2->random = cur1->random->next;
            cur1 = cur2->next;
        }
        
        cur1 = pHead, cur2;
        RandomListNode *head = pHead->next;
        while (cur1) {
            cur2 = cur1->next;
            cur1->next = cur2->next;
            cur1 = cur1->next;
            if (cur1) cur2->next = cur1->next;
        }
        return head;
    }
};