如何做网签合同 网站,网站地图怎么设置,株洲手机网站建设,wordpress两侧悬浮框文章目录 #x1f349;前言#x1f349;题目#x1f349;分析#x1f349;思路一#xff1a;暴力解法#x1f349;思路二#xff1a;很绝的办法 #x1f349;前言
果然#xff0c;力扣的简单题不一定简单#xff0c;但是中等和较难的题一定很麻烦。 这道题相当综合前言题目分析思路一暴力解法思路二很绝的办法 前言
果然力扣的简单题不一定简单但是中等和较难的题一定很麻烦。 这道题相当综合对于思路二如果看完思路后能写出代码那说明你链表掌握得相当熟练了。
题目
题目链接
分析 题干很长不过总结下来就很简单的几句话有一链表它每个节点除了有next还有个random指针random指向哪里不知道可能是其他节点也可能指向NULL。然后现在要你对这样一个链表进行拷贝得到一个新链表新链表中每个节点random的指向和原链表一模一样。 思路一暴力解法
先复制原链表但不复制random指针得到一个新链表。接下来要复制 random 指针那我们得知道它指向原链表的第几个节点假设现在要得到第一个节点 node1 的random指向哪那就遍历链表直到某个节点的地址和 node1-random 一样此时该节点就是 node1 的 random然后要记录这个节点的位置即第几个节点比如 node1 指向第三个节点那你新链表第一个节点也要指向第三个节点。这里注意不是指向原链表的第三个节点如果没有找到那就说明node1-random NULL。 既然现在已经知道第一个节点的 random 指向第三个节点那就遍历新链表先遍历得到第一个节点这里因为刚好是第一个节点所以不用遍历但如果不是第一个那就要遍历了再遍历一次找到第三个节点然后就可以将它的地址赋给random了。 顺便来分析一下时间复杂度最坏的情况是所有节点的 random 都指向最后一个节点此时原链表中每个节点要找n次才能找到random指向的节点有n个节点所以就是n ^ 2而新链表也是如此所以时间复杂度就是ON^2。 这个解法比较复杂代码的话你自行尝试咯。 思路二很绝的办法
之前的难点来源于原链表和新链表之间没有建立起联系。那么我们现在不妨这样拷贝节点放在原链表对应的节点的后面比如拷贝的第一个节点就插在原链表第一和第二个节点之间。最终效果如下图黄色的表示新链表插进来的节点
那么这样做有啥好处呢假设原链表第一个节点的random指向第三个节点那么新链表第一个节点的random 不就是第三个节点的下一个节点了吗 说白了就是把“变”的化为“不变”原先一个节点的random不是随便指吗这就是“变”而我现在可以用这种固定的方式去得到新链表所有节点random指针的指向这是“不变”。
这种解法虽然很巧妙但是写起来也是很麻烦的不过嘛相较于思路一思路二的时间复杂度是ON这就是一个大提升。
第一步先创建新链表的节点然后插入这个操作类似指定位置之后插入。 typedef struct Node Node;Node* cur head;//插入新链表的节点while(cur) {Node* next cur-next; //放循环里面其实是为了防止next为空Node* copy (Node*)malloc(sizeof(Node)); //copy待插入的新节点copy-val cur-val;copy-next next;cur-next copy;cur next;}第二步设置插入节点的random指针记得先将 cur 置为head cur head;while(cur) {Node* copy cur-next;if(cur-random NULL) {copy-random NULL;} else {copy-random cur-random-next; //这一步最关键}cur copy-next;}第三步把新节点取出来连起来就是拷贝后的链表了记得把原链表拼接回去 cur head;Node* newhead NULL,*newtail NULL; //创建新链表然后刚才的新节点进行尾插while(cur) {Node* copy cur-next;if(newhead NULL) {newhead newtail copy;} else {newtail-next copy;newtail newtail-next;}cur copy-next;}return newhead;整个函数的代码
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {Node* cur head;//插入新链表的节点while(cur) {Node* next cur-next; //放循环里面其实是为了防止next为空Node* copy (Node*)malloc(sizeof(Node));copy-val cur-val;copy-next next;cur-next copy;cur next;}//设置新节点的random指针//先重置cur、copycur head; while(cur) {Node* copy cur-next;if(cur-random NULL) {copy-random NULL;} else {copy-random cur-random-next;}cur copy-next;}//把新节点的random处理好之后接下来要把这些新节点与原先节点分离恢复原链表cur head;Node* newhead NULL,*newtail NULL;while(cur) {Node* copy cur-next;if(newhead NULL) {newhead newtail copy;} else {newtail-next copy;newtail newtail-next;}cur copy-next;}return newhead;
}
