本文主要是介绍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.随机链表的复制的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!