朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第138道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!
数据结构与算法专栏:数据结构与算法
个 人 主 页 :stackY、
C 语 言 专 栏:C语言:从入门到精通
LeetCode--138.复制带随即指针的链表:https://leetcode.cn/problems/copy-list-with-random-pointer/description/
目录
1.题目介绍
2.实例演示
3.解题思路
::链接拷贝结点 ::
::找拷贝节点的random ::
:: 拆解拷贝链表 ::
1.题目介绍
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
小编现在这里向大家袒露心扉一下:其实我刚刚看到这个单链表OJ题,看了半天连题目都没咋搞明白,好不容易看懂了题目介绍,可是又不知道该从何下手,然后求助各种大佬,才慢慢理解,然后整理思路,在这篇文章中将这道题分享给大家。
2.实例演示
3.解题思路
这道题应该算是单链表OJ题中比较复杂的一道题了,主要是比较难理解。题目的主要意思就是要拷贝出与原链表一模一样的一个链表。那么这道题拷贝链表都不是很复杂,比较难处理的就是这个随即指针random的指向,如果原链表的random指向空那这好说,拷贝链表的也指向空,但是如果原链表的random指向非空,那该如何去找这个random呢?在这里呢,很多老铁喜欢用random指向的值来比较,这种想法可以,但是架不住链表中有相同的值,那么就有许多老铁用它的random指向的地址来比较,这种方法是完全可行的,但是呢,这种暴力求解的方法往往都不是最优解,使用地址来进行比较的话它的时间复杂度是O(N^2),效率也是不太行。所以我们需要寻求更优解。
这道题的解题思路我分为了三个步骤:
1. 链接拷贝结点:
将拷贝结点插入到原结点的后面。
2. 找拷贝节点的random:
通过原链表来控制拷贝结点的随机指针random。
3. 拆解拷贝链表:
将拷贝结点拆下来,依次尾插组成新的链表,然后恢复原链表。
接下来我们一步一步来进行解题:
::链接拷贝结点 ::
我们可以将拷贝结点链接在原结点的后面,这种方法比较巧妙,有助于我们找随即指针random。
先创建拷贝节点,然后遍历原链表,然后保存头节点的下一个结点,改变指向,将拷贝节点插入到原结点的后面。
图示:
代码演示:
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; //1.链接拷贝节点 while(cur) { //创建拷贝结点 struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; //保存头指针的下一个结点 struct Node* curNext = cur->next; //链接 cur->next = copy; copy->next = curNext; cur = curNext; } //...... }
::找拷贝节点的random ::
当我们将拷贝结点链接在原结点的后面时,我们需要找拷贝结点的随机指针random,这里可以分为两种情况:
1. 如果原结点的random是空,那么直接将拷贝结点的random置为空即可。
2. 若不为空,那么就需要观察一下这个链表,拷贝结点的random指针指向的就是原结点的random指向的结点的next结点:
copy -> random = cur -> random -> next;
因为我们将拷贝结点链接在了原结点的后面,那么原结点的random指向的结点的next结点就是拷贝结点要找的random。我们依旧遍历整个链表,然后将拷贝节点的随机指针链接。
图示:
代码演示:
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; //1.链接拷贝节点 while(cur) { //创建拷贝结点 struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; //保存头指针的下一个结点 struct Node* curNext = cur->next; //链接 cur->next = copy; copy->next = curNext; cur = curNext; } //2.找拷贝节点的random //重新返回头 cur = head; while(cur) { //找拷贝结点 struct Node* copy = cur->next; //找下一个结点 struct Node* next = copy->next; //链接拷贝节点的随机指针random if(cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } //遍历 cur = next; } //...... }
:: 拆解拷贝链表 ::
我们找到了拷贝链表之后呢,需要将这些拷贝的结点组成一个新的链表,这就需要将这些拷贝结点依次进行尾插,然后再将原链表恢复。这就比较简单了:
图示:
完整代码演示:文章来源:https://www.toymoban.com/news/detail-479312.html
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; //1.链接拷贝节点 while(cur) { //创建拷贝结点 struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; //保存头指针的下一个结点 struct Node* curNext = cur->next; //链接 cur->next = copy; copy->next = curNext; cur = curNext; } //2.找拷贝节点的random //重新返回头 cur = head; while(cur) { //找拷贝结点 struct Node* copy = cur->next; //找下一个结点 struct Node* next = copy->next; //链接拷贝节点的随机指针random if(cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } //遍历 cur = 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 == NULL) { copyHead = copyTail = copy; } else { copyTail->next = copy; copyTail = copyTail->next; } //恢复原链表 cur->next = next; cur = next; } return copyHead; }
朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!文章来源地址https://www.toymoban.com/news/detail-479312.html
到了这里,关于单链表OJ题:LeetCode--138.复制带随即指针的链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!