题目

复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 ：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

解答

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) return NULL;

        Node* cur = head;
        unordered_map<Node*, Node*> mapNode;
        //遍历原链表，创建新节点并使用哈希表记录新旧结点的关系
        while(cur != NULL)
        {
            //原结点为key，新节点为value
            mapNode[cur] = new Node(cur->val);
            //继续遍历链表
            cur = cur->next;
        }

        cur = head;
        //再次遍历原链表
        while(cur != NULL)
        {
            //通过map获取新结点的Next，并赋值给新节点的next
            mapNode[cur]->next = mapNode[cur->next];
            //通过map获取新结点的random，并赋值给新节点的random
            mapNode[cur]->random = mapNode[cur->random];
            cur = cur->next;
        }

        return mapNode[head];
    }
};