青岛专业建设网站,门户网站的大数据应用,wordpress获取自定类型,做电商看的网站有哪些内容一、题目#xff1a; 138. 随机链表的复制 - 力扣#xff08;LeetCode#xff09; 函数原型#xff1a; struct Node* copyRandomList(struct Node* head) 二、思路 本题是给出一个单链表#xff0c;单链表的每个结点还额外有一个随机指针#xff0c;随机指向其他结点 138. 随机链表的复制 - 力扣LeetCode 函数原型 struct Node* copyRandomList(struct Node* head) 二、思路 本题是给出一个单链表单链表的每个结点还额外有一个随机指针随机指向其他结点要求复制该链表。 常规情况下复制链表只需要遍历原链表新建和原链表相同的结点尾插到新链表即可。 但是该链表有一个随机指针还需要找到原链表中各个结点随机指针的指向让新链表中结点的随机指针也指向新链表中的与原链表中相同位置的结点。因此还要在新链表中找到原链表中各个结点随机指针指向的结点算法为O(N^2)且判断是否为随机指针指向的结点只能通过结点值判断如果链表中有多个值相同的结点九不便于判断是否为随机指针指向的结点。 上述方法不易实现此处提供一个全新的思路 由于新建一个链表每个结点的随机指针不好复制那么就在原链表上复制每个结点然后再复制每个结点的随机指针。 先在原链表每个结点后复制一个相同的结点复制完成后再次遍历链表就可以通过当前结点随机指针指向结点的下一个结点找到复制结点随机指针需要指向的结点。最后将每个复制的结点从原链表中拆下来重新链接组成新的链表即可完成链表的复制。 三、代码 /*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node*curhead;while(cur)//在原链表每个结点后复制一个相同的结点{struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;copy-nextcur-next;cur-nextcopy;curcur-next-next;}curhead;while(cur){//复制结点的随机指针指向的结点就是当前结点随机指针指向结点的下一结点if(cur-random)cur-next-randomcur-random-next;elsecur-next-randomNULL;curcur-next-next;}curhead;struct Node* newheadNULL;struct Node *tailNULL;while(cur)//拆下复制的结点并恢复原链表重新链接这些结点{struct Node* nextcur-next;cur-nextnext-next;if(tailNULL){newheadtailnext;}else{tail-nextnext;tailnext;}curcur-next;}return newhead;}
