网站开发与软件开发区别,五八58同城找工作,中关村手机在线,深圳创业扶持政策题目描述
题目链接#xff1a;138. 随机链表的复制 - 力扣#xff08;LeetCode#xff09; 题目分析
这个题目很长#xff0c;但是意思其实很简单#xff1a;就是一个单链表#xff0c;每个结点多了一个指针random随机指向链表中的任意结点或者NULL#xff0c;我们血需…题目描述
题目链接138. 随机链表的复制 - 力扣LeetCode 题目分析
这个题目很长但是意思其实很简单就是一个单链表每个结点多了一个指针random随机指向链表中的任意结点或者NULL我们血需要复制这个链表连同random一起复制下来
思路一
思路一是我们用cur遍历链表用for循环找random对应的原链表中的random这个算法找每个random的时间复杂度都是O(N)整个算法的时间复杂度是O(N^2) 思路二
思路二是分三步走
将copy结点链接到原结点的nextcopy结点的random指向对应原结点random的next把copy链表拆接下来尾插到新链表 这个思路更优时间复杂度是O(N)
画图
我们可以简单画图来演示一下这三步
1.copy结点插入到原结点的next 定义cur遍历链表用malloc开辟一个copy的空间然后依次将cur-val赋给copy-val接着将copy结点插入到cur和cur-next之间cur走到copy-.next 2.处理copy结点的random 让cur回到head经过第一步之后我们知道copy就是cur-next这里我们分为两种情况 如果cur-random指向NULL则copy-next也指向NULL否则copy-random指向cur-random-next 然后cur走到cur-next-next 3.copy结点拆解下来进行尾插 最后一步就是尾插定义newhead和tail先指向NULLcur回到headcopy是cur-nextnext保存copy-next 将cpoy尾插到tail将cur-next接到next恢复原链表最后返回newhead 代码示例
我们根据思路二来写代码
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {//copy结点插入到原结点的后面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;}//处理copy结点的randomcurhead;while(cur){struct Node*copycur-next;if(cur-randomNULL){copy-randomNULL;}else{copy-randomcur-random-next;}curcur-next-next;}//copy结点拆下来尾插curhead;struct Node*newheadNULL,*tailNULL;while(cur){struct Node*copycur-next;struct Node*nextcopy-next;if(tailNULL){newheadtailcopy;}else{tail-nextcopy;tailtail-next;}cur-nextnext;curnext;}return newhead;
}
结果同样通过
