题解 | #拷贝有随机指针的链表#

/**
 * 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) {
    // corner case
    if (!head) return nullptr;

    unordered_map<RandomListNode*, RandomListNode*> cloned;
    for (auto p = head; p; p = p->next)
      cloned[p] = new RandomListNode(p->label);

    for (auto p = head; p; p = p->next) {
      cloned[p]->next = cloned[p->next];
      cloned[p]->random = cloned[p->random];
    }

    return cloned.at(head);
  }
};