C语言每日一题：14《数据结构》复制带随机指针的链表

题目一：

题目链接：

思路一：

找相对位置暴力求解的方法：
1.复制一个新的链表出来遍历老的节点给新的节点赋值，random这个时候不去值。
2.两个链表同时遍历，遍历老链表的时候去寻找相对位置，在遍历新的链表找到随机值赋值。

struct Node* copyRandomList(struct Node* head) {struct Node* cur=head;struct Node* newhead=NULL,*tile=NULL;//复制原来的链表数据while(cur){//开辟新的节点struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));newnode->val=cur->val;newnode->next=NULL;newnode->random=NULL;if(newhead==NULL){tile=newhead=newnode;}else{tile->next=newnode;tile=tile->next;}cur=cur->next;}//进行两个的循环遍历，找相对位置cur=head;struct Node* cur2=newhead;int pos=0;while(cur){//更新一下pospos=0;//cur的随机值是哪一个struct Node* find=cur->random;if(find==NULL){cur2->random=NULL;cur=cur->next;cur2=cur2->next;continue;}else{struct Node* curold=head;while(curold){if(find==curold){break;}pos++;curold=curold->next;}}//寻找随机节点struct Node* curnew=newhead;while(pos){curnew=curnew->next;pos--;}cur2->random=curnew;//循环条件cur=cur->next;cur2=cur2->next;}return newhead;
}

思路二:

struct Node* copyRandomList(struct Node* head) {struct Node* cur = head, * tile = NULL;//新的链表赋值插入,cur为空才结束插入while (cur){//保存下一个老的tile = cur->next;struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));newnode->val = cur->val;cur->next = newnode;newnode->next = tile;//循环条件cur = tile;}//给copy链表赋值randomstruct Node* copy = NULL;cur = head;tile = NULL;while (cur){//连接了新的节点copy = cur->next;tile = copy->next;//给random赋值，随机值，正常值的两个情况if (cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}//循环的移动cur = tile;}copy = NULL;cur = head;tile = NULL;//分离链表struct Node* newhead = NULL;struct Node* move = NULL;while (cur){copy = cur->next;tile = copy->next;if (newhead == NULL){newhead = copy;move = newhead;}else{move->next = copy;move = move->next;}//恢复原来的节点cur->next = tile;//循环遍历cur = tile;}return newhead;}