💯💯💯
本篇总结链表如何深度拷贝，考虑链表拷贝后地址不能相同，采用一种独特的方式来拷贝原链表的相对位置，图文分析，更好理解。
⏰.链表深度拷贝
深度拷贝指的是将该链表上每个结点都拷贝过来，链接形式是与原链表一模一样。
但要注意的是，拷贝的链表的链接形式虽然跟原链表一样，但它们的地址都是不同的，拷贝的链表中的指针都不应该指向原链表中的结点。
而解答本题的思路就是：
1.在每个结点的后面生成自己的拷贝结点
2.处理每个拷贝结点的random
3.将所有拷贝结点拿下来，尾插形成新的链表
4.恢复原链表链接关系
🕑生成拷贝结点
//1.在每个结点的后面生成拷贝结点 struct Node* cur = head;//利用cur进行遍历，不使用head遍历 while (cur) { struct Node* next = cur->next;//记录后面结点的位置 struct Node* copy = (struct Node*)malloc(sizeof(struct Node));//开辟一个结点出来 copy->val = cur->val;//将原结点的数据拷贝过去 //cur copy next现在就是要求这个样子，cur第一个结点，copy要插在cur和next在中间 cur->next = copy; copy->next = next; //插入结点 cur = next;//迭代操作 }
🕒处理random
//2.处理每个拷贝结点的random cur = head;//将cur重新指回头结点 while (cur) { struct Node* copy = cur->next;//记录每个拷贝结点的位置 if (cur->random == NULL)//如果原结点的random为NULL { copy->random = NULL;//则拷贝结点的random也为NULL } else { copy->random = cur->random->next;//否则拷贝结点的random就等于原结点random的next。 } cur = cur->next->next;//cur每次要走两步，因为这样才可以每次都走到原结点上去，然后原结点的next就是拷贝结点 }
🕓解下拷贝结点
//3.解下拷贝结点，恢复原来结点链接 cur = head;//使cur重新指向头结点 struct Node* copyhead = NULL, * tail = NULL;//因为拷贝结点需要尾插成一条链表，需要头结点和找尾操作 while (cur) { //解下拷贝结点就是把结点拿下来尾插.尾插需要头指针尾指针 struct Node* copy = cur->next;//记录每个拷贝结点 struct Node* next = copy->next;//记录每个原来结点 if (copyhead == NULL)//一开始新链表头结点是空所以需要将第一个拷贝结点赋值过去 { copyhead = tail = copy; } else { tail->next = copy;//接下来才是真正的尾插，将拷贝结点尾插到tail结点的next上去 tail = tail->next;//tail结点每次都需要更新，以便找尾 } //恢复链接关系 cur->next = next;//next记录的是每个copy结点的下一个那就是原结点，原结点与cur链接恢复原来链接关系 //迭代 cur = next; }
⏰.完整代码
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { //1.在每个结点的后面生成拷贝结点 struct Node* cur = head; while (cur) { struct Node* next = cur->next; struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; //cur copy next cur->next = copy; copy->next = next; //插入结点 // 迭代 cur = next; } //2.处理每个拷贝结点的random cur = head; while (cur) { struct Node* copy = cur->next; if (cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = cur->next->next; } //3.解下拷贝结点，恢复原来结点链接 cur = head; struct Node* copyhead = NULL, * tail = NULL; while (cur) { //解下拷贝结点就是把结点拿下来尾插.尾插需要头指针尾指针 struct Node* copy = cur->next; struct Node* next = copy->next; if (copyhead == NULL) { copyhead = tail = copy; } else { tail->next = copy; tail = tail->next; } //恢复链接关系 cur->next = next; //迭代 cur = next; } return copyhead; }
