【Leedcode】数据结构中链表必备的面试题（第五期）

【Leedcode】数据结构中链表必备的面试题（第五期）

---

---

1.题目

138. 复制带随机指针的链表： 如下（示例）：

给你一个长度为n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。
新节点的next指针和random指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
复制链表中的指针都不应指向原链表中的节点 。  返回复制链表的头节点。

简单来说：复制原来的链表（新的），返回新链表的头结点

---

---

---

2.思路+图解

（1）第一步：复制每一个结点，插入到原结点和下一个结点之间

---

第一步代码实现 ： 如下（示例）：

//1.第一步：先把原来的拷贝一份struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy -> next = cur -> next;cur -> next = copy;copy -> val = cur -> val;cur = copy -> next;}

---

（2）第二步：根据原结点random，处理复制结点的random

这里要注意：复制完之后的random所指向的是复制之前random的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 = copy -> next;}

---

（2）第三步：复制结点解下来连接成一个新链表，恢复原链表链接关系

---

---

第三步代码实现 ： 如下（示例）：

 // 3.第三步：把拷贝结点解下来，链接成新的链表，同时恢复原链表cur = head;struct Node* copyhead = NULL ,*copytail =NULL;while(cur){struct Node* copy = cur -> next;struct Node* next = copy -> next;if(copytail == NULL){copytail = copyhead = copy;}else{copytail -> next = copy;copytail = copy;}//恢复原链表的犍cur -> next = next;cur = next ;}

---

3.整体源代码

整体源代码 ： 如下（示例）：

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* copy = (struct Node*)malloc(sizeof(struct Node));copy -> next = cur -> next;cur -> next = copy;copy -> val = cur -> val;cur = copy -> 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 = copy -> next;}// 3.第三步：把拷贝结点解下来，链接成新的链表，同时恢复原链表cur = head;struct Node* copyhead = NULL ,*copytail =NULL;while(cur){struct Node* copy = cur -> next;struct Node* next = copy -> next;if(copytail == NULL){copytail = copyhead = copy;}else{copytail -> next = copy;copytail = copy;}//恢复原链表的犍cur -> next = next;cur = next ;}return copyhead;
}

---

总结

以上就是今天要讲的内容，本文介绍了【Leedcode】数据结构中链表必备的面试题（第五期）。
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！