难度：中等

题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

解答

思路

分两次复制，第一次复制val和next，第二次复制random
保存新旧链表地址，使用 find 函数找到random对应的节点。

知识点

find 函数的使用

代码

/*
// 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){return nullptr;}Node* saveHead=head;Node* newHead;Node* tempNode=new Node(head->val);Node* nextNode=nullptr;vector<Node*> oldList;vector<Node*> newList;newHead=tempNode;while(head->next){oldList.push_back(head);newList.push_back(tempNode);head=head->next;nextNode=new Node(head->val);tempNode->next=nextNode;tempNode=nextNode;} oldList.push_back(head);newList.push_back(tempNode);head=saveHead;Node* saveNewHead=newHead;while(head){auto it = find(oldList.begin(),oldList.end(),head->random);if(it!=oldList.end()){newHead->random=newList[it-oldList.begin()];}head=head->next;newHead=newHead->next;}return saveNewHead;}
};