复制带随机指针的链表😫
实话实说,这倒是我进入数据结构之后遇见的最难的题了😫.
暴力解法
暴力的解法一定是不如巧方法效率高，但是这种方法还是很锻炼人的思想的，比如我就在一个野指针里载了一个下午🤣。
思路讲解
struct Node* copyhead = (struct Node*)malloc(sizeof(struct Node));//复制链表的头 struct Node* prev = copyhead;//用于开辟复制链表的变量后续不用了 struct Node* cur = head->next;//从第二个空间开始复制 copyhead->val = head->val; copyhead->next = NULL; //解决val和链表空间 while(cur != NULL) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; prev->next = copy; prev = copy; cur = cur->next; copy->next = NULL; }
首先头指针判空就不赘述，上述代码主要是为了给我们复制链表空间，并把val付给我们的拷贝空间。值得注意的是
上图的置空其实非常关键，如果不置空就会得到
心脏骤停😢😢😢。所以链表末尾置空大家一定要重视起来啊！！！！！！😢
短短的两行置空让舒文痛失一个下午的学习时光😢。
//解决随机指针问题 int num = 0;//用于下标表达 struct Node* copycur = copyhead; cur = head; struct Node* tmp = head;//用于寻找random while(cur != NULL&©cur!=NULL) { num = 0; if(cur->random == NULL) { copycur->random = NULL; } else { tmp = head; num = 0; while(tmp != cur->random) { tmp = tmp->next; num++; } tmp = copyhead; while(num) { tmp = tmp->next; num--; } copycur->random = tmp; } copycur = copycur->next; cur = cur->next; } return copyhead;
主要部分就是这块解决随机指针的问题了，我使用的计数器的方法，用num充当类似数组中下标的作用。通过遍历原链表中random指向的下标位置，我们就可以在我们拷贝数组哪里也让他指向相同下标的链表节点位置。然后让原链表向下移动，拷贝链表向下移动即可
结束。
暴力求解也是很有意思的解法大家可以试试哦~
正确代码
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { if(head == NULL) { return NULL; } struct Node* copyhead = (struct Node*)malloc(sizeof(struct Node));//复制链表的头 struct Node* prev = copyhead;//用于开辟复制链表的变量后续不用了 struct Node* cur = head->next;//从第二个空间开始复制 copyhead->val = head->val; copyhead->next = NULL; //解决val和链表空间 while(cur != NULL) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; prev->next = copy; prev = copy; cur = cur->next; copy->next = NULL; } //解决随机指针问题 int num = 0;//用于下标表达 struct Node* copycur = copyhead; cur = head; struct Node* tmp = head;//用于寻找random while(cur != NULL&©cur!=NULL) { num = 0; if(cur->random == NULL) { copycur->random = NULL; } else { tmp = head; num = 0; while(tmp != cur->random) { tmp = tmp->next; num++; } tmp = copyhead; while(num) { tmp = tmp->next; num--; } copycur->random = tmp; } copycur = copycur->next; cur = cur->next; } return copyhead; }
巧方法
巧方法的思路其实也是比较简单的.
先创建链表并附在原链表的后面.
如图:
这也是下面代码所实现的👍
struct Node* cur = head; while(cur!=NULL) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = cur->next->next; }
记得把新创的空间放在原链表后记得让cur走两步才能到下一个原链表元素上
然后对cur进行赋值成head让他继续搞随机指针🤪.
先看看代码吧
cur = head; while(cur != NULL) { if(cur->random == NULL) { cur->next->random = NULL; cur = cur->next->next; } else { cur->next->random = cur->random->next; cur = cur->next->next; } }
这串代码其实思想也十分简单原本链表的random所指向的位置的下一位及next就是我们想让我们拷贝链表的random指向的位置🤪.
最后一步,将链表拆下来.
这一步最难搞了😫
将copy的链表拆下时要注意一下细节
cur = head; struct Node* copyhead = head->next; struct Node* copytail = copyhead; if(copyhead->next==NULL) { return copyhead; } while(cur!=NULL) { struct Node* copy = cur->next; struct Node* curnext = copy->next; copytail->next = copy; copytail = copy; cur->next = curnext; cur = curnext; }
我们将他拆下时要用copyhead来保存头部位置对要拆下的部分使用类似于尾插的形式,然后我们使用变量保存的方式将原链表恢复成原本的模样.
好这样整体思路就确定下来了🤪.
用copy来确定要搬用的空间的位置.
用curnext来确定原链表的的下一个空间的位置.
copytail用于尾插时的控制.
但是这样的循环解决不了单单一个空间的情况不过这种情况我们一个if就可以解决了.
正确代码
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { if(head==NULL) { return NULL; } struct Node* cur = head; while(cur!=NULL) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = cur->next->next; } cur = head; while(cur != NULL) { if(cur->random == NULL) { cur->next->random = NULL; cur = cur->next->next; } else { cur->next->random = cur->random->next; cur = cur->next->next; } } cur = head; struct Node* copyhead = head->next; struct Node* copytail = copyhead; if(copyhead->next==NULL) { return copyhead; } while(cur!=NULL) { struct Node* copy = cur->next; struct Node* curnext = copy->next; copytail->next = copy; copytail = copy; cur->next = curnext; cur = curnext; } return copyhead; }
结尾
机器人🤤,嘿嘿,.🤤.舒文最爱机器人了🤤.
