网页设计开题报告怎么写_马来西亚服务器租用_seo关键字优化软件_无锡seo

题目描述：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

输入输出样例：

示例 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]]

提示：
0 <= n <= 1000
-10⁴ <= Node.val <= 10⁴
Node.random 为 null 或指向链表中的节点。

题解：

解题思路：

思路一（哈希表+标号）：

1、在复制随机链表时，val和next的指向是可以很容易深拷贝复制出来的，而random的指向的复制不好实现，解决此问题的关键是怎么复制出对应的random的指向，我们可以想到一种对链表结点进行标号的思想。
例：

我们可以使用两个哈希表记录两个链表中每个结点的地址和序号的对应关系。我们通过原随机链表的random指向可知道两个random连接前后节点的序号，如13的random的指向7，那1序号指向0序号，那我们就可以通过其来更改复制出的随机链表的指向。

2、具体思路如下：
① 创建两个哈希表用于存储两个链表结点地址与序号的对应关系。
② 遍历原链表的同时创建复制链表的val和next的指向，将random指向设为nullptr，并使用哈希表记录原链表结点地址和序号的对应关系和复制链表序号和结点地址的对应关系。
③ 用两个哈希表更新复制链表的random指向

2、复杂度分析：
① 时间复杂度：O(N)，N代表原链表所含结点的数量。创建复制结点的时间复杂度为N，更新结点的指向的时间消耗为N，所以时间复杂度为O（N）。
② 空间复杂度：O(N)，使用了两个额外的哈希表来存储结点地址和序号的对应关系（除存储答案所需空间）。

思路二（哈希表+原结点与复制结点的对应关系）：

1、通过思路一（哈希表+标号）的实现我们进而能想到直接将原链表和复制链表中对应的结点存储在哈希表中，这样我们就可以直接通过原地址的random来更新复制链表的指向。
例：

我们将7的原结点的地址与复制结点的地址的对应关系存入哈希表中，其他结点也进行同样的操作，这样我们就能通过原结点的random指向来直接更新复制链表中random的指向。如原链表中13的random指向7，那我们通过哈希表也能将复制链表中13的random指向7。

2、具体思路如下：
① 创建一个哈希表用于存储两个链表中每个结点地址的对应关系。
② 遍历原链表的同时创建复制链表的val和next的指向，将random指向设为nullptr，并使用哈希表记录原链表结点地址和复制链表地址的对应关系。
③ 用过哈希表更新复制链表的random指向。

3、复杂度分析
① 时间复杂度：O(N)，N代表原链表所含结点的数量。创建复制结点的时间复杂度为N，更新结点的指向的时间消耗为N，所以时间复杂度为O（N）。
② 空间复杂度：O(N)，，使用了一个额外的哈希表来存储结点地址的对应关系（除存储答案所需空间）。

思路三（迭代 + 节点拆分）：

1、我们可以将复制结点创建出来之后直接插入在原结点后边。这样我们在更新random的指向时就可以直接通过原结点random的指向来更新复制结点random的指向。
例：

2、具体思路如下：
① 在每个原结点后边创建一个复制结点并插入，将复制结点的random设置为nullptr。
② 遍历创建后的链表，更新复制结点的random的指向。
③ 将复制结点查下来，将原链表进行复原。

3、复杂度分析
① 时间复杂度：O(N)，N代表原链表所含结点的数量。创建复制结点的时间复杂度为N，更新结点的指向的时间消耗为N，所以时间复杂度为O（N）。
② 空间复杂度：O(1)，除存储答案所需空间。

代码实现

代码实现（思路一（哈希表+标号））：

/*方法一（哈希表） 
使用哈希表存储结点地址与其对应的序号 
*/ 
Node* copyRandomList1(Node* head) {Node *head1=head,*head2=nullptr,*tail2=nullptr;//结点的序号从零开始int i=0;//存储原链表地址和序号的对应关系（通过地址 -> 序号）unordered_map<Node *,int> head1_address_id;//复制链表序号和地址的对应关系（通过序号 -> 地址）unordered_map<int,Node *> head2_id_address;//采用尾插法创建复制链表//首先创建一个新的随机链表二，链表二的val和next与随机链表一(head)相同,random为nullptr ，在创建过程中保存两个链表序号和地址的对应关系while(head1!=nullptr){Node *newNode=new Node(head->val);if(head2==nullptr){head2=tail2=new Node(head1->val);}else{tail2->next=new Node(head1->val);tail2=tail2->next;}//保存链表一中结点地址与序号的对应关系 head1_address_id[head1]=i;//保存链表二中序号和结点地址的对应关系 head2_id_address[i]=tail2;head1=head1->next;++i;}//更新head1指向原链表的首节点head1=head;//tmp_head2，用于暂时保存head2的首结点 Node *tmp_head2=head2;//更新链表二的random的指向 while(head1!=nullptr){//如果链表一中结点random的指向为nullptr，则链表二的复制节点的random无需修改 if(head1->random==nullptr){head1=head1->next;head2=head2->next;continue;}//通过链表一中结点的random找到对应结点的id，通过此id来更新链表二的random的指向 int i=head1_address_id[head1->random];head2->random=head2_id_address[i];head1=head1->next;head2=head2->next;}return tmp_head2;
}

代码实现（思路二（哈希表+原结点与复制结点的对应关系））：

Node* copyRandomList2(Node* head) {Node *head1=head,*head2=nullptr,*tail2=nullptr;unordered_map<Node *,Node *> head1_head2;//采用尾插法创建复制链表//首先创建一个新的随机链表二，链表二的val和next与随机链表一(head)相同,random为nullptr ，在创建过程中保存两个链表地址的对应关系while(head1!=nullptr){Node *newNode=new Node(head->val);if(head2==nullptr){head2=tail2=new Node(head1->val);}else{tail2->next=new Node(head1->val);tail2=tail2->next;}//保存原结点地址和复制结点地址的对应关系 head1_head2[head1]=tail2;head1=head1->next;}//更新head1指向原链表的首节点head1=head;//tmp_head2，用于暂时保存head2的首结点 Node *tmp_head2=head2;//更新链表二的random的指向 while(head1!=nullptr){//如果链表一中结点random的指向为nullptr，则链表二的复制节点的random无需修改 if(head1->random==nullptr){head1=head1->next;head2=head2->next;continue;}//通过链表一中结点的random找到对应结点的地址，通过此对应结点地址来更新链表二的random的指向 Node *tmp=head1->random;head2->random=head1_head2[tmp];head1=head1->next;head2=head2->next;}return tmp_head2;
}

代码实现（思路三（迭代 + 节点拆分））：

Node* copyRandomList3(Node* head) {if (head == nullptr) {return nullptr;}Node* head1 = head;// 创建复制的结点插入原链表while (head1 != nullptr) {Node* newNode = new Node(head1->val);newNode->next = head1->next;head1->next = newNode;head1 = head1->next->next;}//更新head1指向首节点head1 = head;// 修改新创建结点random的指向while (head1 != nullptr) {if (head1->random != nullptr) {head1->next->random = head1->random->next;}head1 = head1->next->next;}//将链表一和链表二进行拆分,不使用新的头节点 head1 = head;Node* head2 = head->next;Node* tmp_head2 = head->next;while (head2->next != nullptr) {head1->next = head1->next->next;head2->next = head1->next->next;head1 = head1->next;head2 = head2->next;}head1->next = nullptr;return tmp_head2;//将链表一和链表二进行拆分//使用一个新的头节点来链接拆分的链表二 //	Node *dummyNode=new Node(0);//	head1=head;//	Node *head2=dummyNode;//	while(head1!=nullptr){//		head2->next=head1->next;//		head2=head1->next;//		head1->next=head2->next;//		head1=head2->next;//	}//	head2=dummyNode->next;//	delete dummyNode;//	return head2;}

以思路二为例完成代码调试

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;class Node{
public:int val;Node *next;Node *random;Node(int _val){val=_val;next=NULL;random=NULL;}
};/*创建随机链表*/ 
Node *createNode(vector<vector<int>> &arr){Node *head=nullptr,*tail=nullptr;int n=0;//id_adress保存每个结点的序号和id，使其对应 unordered_map<int,Node *> id_adress;//采用尾插法先创建一个单链表，先使得random=nullptr for(const auto &i:arr){if(head==nullptr){head=tail=new Node(i[0]);}else{tail->next=new Node(i[0]);tail=tail->next;}id_adress[n]=tail;++n;}//将random通过adress_id进行赋值，-1代表nullptr tail=head;for(const auto &i:arr){if(i[1]==-1){tail=tail->next;continue;}tail->random=id_adress[i[1]];tail=tail->next;}return head;
}/*方法二（哈希表+原结点与复制结点的对应关系） 
使用额外空间 
*/ 
Node* copyRandomList2(Node* head) {Node *head1=head,*head2=nullptr,*tail2=nullptr;unordered_map<Node *,Node *> head1_head2;//首先创建一个新的随机链表二，链表二的val和next与随机链表一(head)相同,random为nullptr while(head1!=nullptr){Node *newNode=new Node(head->val);if(head2==nullptr){head2=tail2=new Node(head1->val);}else{tail2->next=new Node(head1->val);tail2=tail2->next;}//保存原结点地址和复制结点地址的对应关系 head1_head2[head1]=tail2;head1=head1->next;}head1=head;//tmp_head2，用于暂时保存head2的首结点 Node *tmp_head2=head2;//更新链表二的random的指向 while(head1!=nullptr){//如果链表一中结点random的指向为nullptr，则链表二的复制节点的random无需修改 if(head1->random==nullptr){head1=head1->next;head2=head2->next;continue;}//通过链表一中结点的random找到对应结点的地址，通过此对应结点地址来更新链表二的random的指向 Node *tmp=head1->random;head2->random=head1_head2[tmp];head1=head1->next;head2=head2->next;}return tmp_head2;
}int main(){vector<vector<int>> a={{7,-1},{13,0},{11,4},{10,2},{1,0}};//创建原随机链表Node *head =createNode(a);//随机链表的复制Node *test =copyRandomList1(head);//只输出复制随机链表的random指向while(test!=nullptr){if(test->random!=nullptr){cout<<test->random->val<<"   ";}else{cout<<"nullptr   ";}test=test->next;}cout<<"null"; return 0;
}

LeetCode 热题 100_随机链表的复制（32_138)原题链接
欢迎大家和我沟通交流(✿◠‿◠)