网站开发教程免费,买购网官方网站,单县网站定制,海外宣传推广实施方案目录
题目链接
题目分析 题目定位#xff1a;
解题思路
解题思路1#xff08;粗暴但是复杂度高#xff09; 解题思路2#xff08;巧妙并且复杂度低#xff09; 题目链接
138. 复制带随机指针的链表https://leetcode-cn.com/problems/copy-list-with-random-pointer/ …目录
题目链接
题目分析 题目定位
解题思路
解题思路1粗暴但是复杂度高 解题思路2巧妙并且复杂度低 题目链接
138. 复制带随机指针的链表https://leetcode-cn.com/problems/copy-list-with-random-pointer/ 题目分析 题目定位 本题属于链表中较为综合的题目考验做题者的思想以及用代码实现的能力能够真正理解并做出此题需要对链表有相对熟练的掌握度。 话不多说先来分析题目 题目是想让我们构造一个链表的拷贝也就是开辟一块一模一样的链表但是本题中的链表又和普通的单链表不一样如图 我们发现链表中每一个节点中的结构体成员除了val和next之外还有一个random而random是指向链表中的任意一个节点甚至可以是NULL。 因此要拷贝这个链表的难度就在于如何使拷贝的链表中每一个节点的random指向其对应的节点呢 解题思路
解题思路1粗暴但是复杂度高
第1步.先忽略原链表的random指针对其进行复制如图 (1)定义两个struct Node*类型的指针copyhead和copytail来储存复制链表的头和尾并初始化为NULL并且定义一个struct Node*类型的指针cur指向head (2)若原链表不为空则此时cur指向第一个节点。用malloc开辟一块空间作为复制的第一个节点并定义一个copy指针来保存并将copy-val改为cur-val并让copyhead和copytail指向copy节点 (3)让cur移向下一个节点。用malloc开辟一块空间作为复制的第二个节点并让copy指向它并将copy-val改为cur-val先让copytail-next指向copy来连接两个节点再让copytail指向copy节点(更新尾节点)。 像这样一直循环下去直到cur指向NULL循环结束最后再让copytail-next NULL此时便完成了第一步的复制操作 此时我们便可以根据图解来写代码 struct Node* copyRandomList(struct Node* head) {//1.忽略random复制链表struct Node* cur head;struct Node* copyhead NULL;struct Node* copytail NULL;while(cur){struct Node* copy (struct Node*)malloc(sizeof(struct Node))copy-val cur-val;if(copyhead NULL){copyhead copy;copytail copy;}else{//先连接copytail-next copy;//再指向copycopytail copy;}cur cur-next;}copytail-next NULL;
} 第2步.处理拷贝链表的random指针 (1)查找原链表中的random指向的节点到底是第几个节点并定义一个变量pos来记录下来 ①如果原链表random指向NULL则不需要找pos ②如果原链表的random指向链表中的节点每次循环开始可以初始化一个新的指针newcurhead再对newcur进行迭代每当newcur向后走一次pos加一直到newcur cur-random的时候循环结束举一个例子 (2)用一个循环来使拷贝链表中random指向其对应的节点 ①如果原链表的random指向NULL那么便很简单拷贝的random直接置为NULL ②如果原链表的random指向链表中的节点每次循环开始可以初始化一个新的指针newcopycopyhead,那么拷贝的random则可以通过一个循环来找到pos所对应的第几个节点接着上面的例子 根据图解我们可以写出代码 struct Node* copyRandomList(struct Node* head) {//1.忽略random复制链表struct Node* cur head;struct Node* copyhead NULL;struct Node* copytail NULL;while (cur){struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;if (copyhead NULL){copyhead copy;copytail copy;}else{//先连接copytail-next copy;//再指向copycopytail copy;}cur cur-next;copytail-next NULL;}//2.处理拷贝链表的random指针cur head;struct Node* copy copyhead;while (cur){int pos 0;if (cur-random NULL){copy-random NULL;}//找到cur的random指向对应的第几个节点else{//让newcur和newcopy重新指向第一个节点struct Node* newcur head;struct Node* newcopy copyhead;while (newcur ! cur-random){newcur newcur-next;pos;}//使copy的random指向对应的第pos个节点while (pos--){newcopy newcopy-next;}copy-random newcopy;}//cur和copy向后走cur cur-next;copy copy-next;}return copyhead;
} 题解一总结优点是这种思路比较容易想到并且理解缺点是由于找到原链表找到random指向的节点的pos的过程每个节点的复杂度为O(n)又有n个节点因此这种解法的时间复杂度为O(n²)并不是一个优秀的解法接下来将为大家讲另一种优秀的解法。 解题思路2巧妙并且复杂度低
第1步 把拷贝节点连接再原节点的后面 用这种方式处理是为了方便找到拷贝链表的random应该指向第几个节点random指向的这个节点的下一个节点就是拷贝链表要找的random节点 根据图解我们可以写出代码 //1.链接链表struct Node* cur head;while(cur){//提前储存原链表下一个节点的地址struct Node* next cur-next;//为原链表的拷贝开辟空间struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;//链接原链表和拷贝节点cur-next copy;copy-next next;//迭代往下走cur next;} 第2步 拷贝原链表的random节点 (1)若原链表的节点的random指向NULL拷贝节点的random也指向NULL (2)若原链表的节点random指向原链表的其中一个节点那么random指向的这个节点的下一个节点就是拷贝链表要找的random以原链表二个节点为例 (3)实现后题解如下 根据图解我们可以写出代码 //2.拷贝原链表的random节点cur head;while(cur){struct Node* copy cur-next;if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur copy-next;} 第3步 将拷贝节点与原链表分开 (1)用cur和copy指针来分别使原链表和拷贝链表的节点向后迭代由于copy随着cur向后迭代一直跟在cur的后面 因此循环外初始化cur head循环内初始化copy cur-next; (2)为原链表定义一个next来连接链表为拷贝链表定义一个copyhead和copytail来返回和连接链表当原链表第一个节点不为空才能保证copy的第一个节点不为空因此copyhead和copytail先置空 循环外初始化copytail copyhead NULL循环内初始化next copy-next, (3)当cur指向第一个节点时进入循环此时copyhead和copytail为空使其指向拷贝链表的第一个节点再使cur-next next将cur和next连接起来并使curnext往后走 若cur不为空再之后就是让copycur-nextnext copy-next 捋清楚结构就可以写出循环体框架 cur head;struct Node* copyhead NULL;struct Node* copytail NULL;while(cur){struct Node* copy cur-next;struct Node* next copy-next;if(copyhead NULL){copyhead copytail copy;}cur-next next;cur next;} (4)当cur指向第二个节点时copyhead和copytail此时不为空copy也指向拷贝的第二个节点因此用copytail-next copy连接两节点再使copytail copy使其向后迭代 捋清关系我们便可以补全循环体 //3.将拷贝节点与原链表分开cur head;struct Node* copyhead NULL;struct Node* copytail NULL;while(cur){struct Node* copy cur-next;struct Node* next copy-next;if(copyhead NULL){copyhead copytail copy;}else{copytail-next copy;copytail copy;}cur-next next;cur next;} 完整代码
struct Node* copyRandomList(struct Node* head) {//1.链接链表struct Node* cur head;while(cur){//提前储存原链表下一个节点的地址struct Node* next cur-next;//为原链表的拷贝开辟空间struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;//链接原链表和拷贝节点cur-next copy;copy-next next;//迭代往下走cur next;}//2.拷贝原链表的random节点cur head;while(cur){struct Node* copy cur-next;if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}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(copyhead NULL){copyhead copytail copy;}else{copytail-next copy;copytail copy;}cur-next next;cur next;}return copyhead;
} 题解二总结由于第二种解题思路用巧妙的连接方式使拷贝链表的random不需要通过对原链表的每一个节点遍历也能找到大大降低了时间复杂度这种解法的时间复杂度为O(n)。
