定制网站型网站开发,如何做好营销型网站用户体验,wordpress图片延迟,网站追踪如何做深拷贝#xff0c;是指将该链表除了正常单链表的数值和next指针拷贝#xff0c;再将random指针进行拷贝 想法一 先拷贝出一份链表#xff0c;再对于每个节点的random指针#xff0c;在原链表进行遍历#xff0c;找到random指针的指向#xff0c;最后完成拷贝链表random… 深拷贝是指将该链表除了正常单链表的数值和next指针拷贝再将random指针进行拷贝 想法一 先拷贝出一份链表再对于每个节点的random指针在原链表进行遍历找到random指针的指向最后完成拷贝链表random的指向 时间复杂度O(N^2) 想法二 下面这种方法是使用C语言的最优解 时间复杂度O(N) 完整代码如下
struct Node* copyRandomList(struct Node* head)
{//1.拷贝节点插入原节点的后面struct Node* cur head;while (cur){struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;struct Node* next cur-next;copy-next next;cur-next copy;cur next;}//2.控制拷贝节点的randomcur head;while (cur){struct Node* copy cur-next;if (cur-random){copy-random cur-random-next;}else{copy-random NULL;}cur copy-next;}//3.拷贝节点解下来组成拷贝链表恢复原链表cur head;struct Node* copyHead NULL;struct Node* copyTail NULL;while (cur){struct Node* copy cur-next;struct Node* next copy-next;if (copyTail){copyTail-next copy;copyTail copyTail-next;}else{copyHead copyTail copy;}cur-next next;cur next;}return copyHead;
}
