138.随机链表的复制

本文主要是介绍138.随机链表的复制，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {Node* cur=head;//拷贝节点插入到原节点后面while(cur){Node* copy=(Node*)malloc(sizeof(Node));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}//链接randomcur=head;while(cur){Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=copy->next;}//放入新链表中Node* copyHead=NULL,*copyTail=NULL;cur=head;while(cur){Node* copy=cur->next;if(copyTail == NULL){copyHead=copyTail=copy;}else{copyTail->next=copy;copyTail=copyTail->next;}cur=copy->next;}return copyHead;}

总体思路是：
先将拷贝节点插入原节点的后面然后让random指向该指向的位置，创建新链表把拷贝节点放入新链表中。

创建拷贝节点，把每个原节点的拷贝节点放到原节点的后面。用malloc函数创建一个新节点，让copy里面的值等于cur里面的值，然后进行单链表的插入就可以了。

这里就是这个代码的核心了。
创建临时变量copy，头节点为cur从头遍历把cur的next当作新复制的节点也就是copy。如果cur的random指向NULL，那么复制节点copy的random也指向NULL。另一种情况是cur的rondom指向下一个cur，那么copy的random也将指向下一个copy的random。

最后将拷贝节点放入一个新链表中。

这篇关于138.随机链表的复制的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---