LeetCode|剑指offer_复杂链表的复制(C++_三种方法_时间O(N^2)空间O(1)_复杂问题的拆分 / 时间O(N)空间(N)_哈希表_图解映射 / 时间O(N)空间(1)

原题链接

文章图片

文章目录

- 1.方法一：复杂问题的拆分
- C/C++代码
- 时间复杂度与空间复杂度
- 2.方法二：哈希表储存原链表与复制链表的关系(空间换时间)
- C++代码
- 时间复杂度与空间复杂度
- 3.方法三：不把链表分成两份，先复制在拆分链表
- C++代码
- 时间复杂度与空间复杂度

1.方法一：复杂问题的拆分这种思路非常的简到直白，就是将复杂问题拆分开。先复制next节点，最后再复制随机节点random
注意：
1.在复制随机节点random时，因为这个节点指向的未知是随机的，所以每次找random指向的节点时要从头节点开始找起。
2.random指针可能为空指针，在写代码时要进行判断
定义两个节点指针，一个指向原链表的头节点s，另一个指向复制的链表的头节点sc，讲pNode这个位置的random保存起来tmp。当s!=tmp时说明还没有找到这个节点的random，s向下移动，sc向下移动。当s==tmp时表明sc也找到了复制链表这个节点的random指针

LeetCode|剑指offer_复杂链表的复制(C++_三种方法_时间O(N^2)空间O(1)_复杂问题的拆分 / 时间O(N)空间(N)_哈希表_图解映射 / 时间O(N)空间(1)_链表拆分)

文章图片

C/C++代码

/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution {public: RandomListNode* Clone(RandomListNode* pHead) {if(pHead==nullptr) return pHead; RandomListNode*pNode=pHead; RandomListNode*cloneNode=nullptr; RandomListNode*cloneHead=nullptr; while(pNode!=nullptr)//先复制next指针，成单链表再复制random指针 {RandomListNode*tmp=new RandomListNode(pNode->label); if(cloneHead==nullptr)//注意判断第一个节点复制的情况 cloneHead=cloneNode=tmp; else{cloneNode->next=tmp; cloneNode=cloneNode->next; } pNode=pNode->next; } pNode=pHead; cloneNode=cloneHead; while(pNode!=nullptr) {RandomListNode*radom=pNode->random; //把原链表的random记录下来 RandomListNode*sc=cloneHead; //每次从头开始找random if(radom!=nullptr) {RandomListNode*s=pHead; //每次从头开始找random while(s!=radom)//注意复制的random可能为空指针 {s=s->next; sc=sc->next; } }//递归结束后sc为复制链表的random if(radom==nullptr) cloneNode->random=nullptr; else cloneNode->random=sc; cloneNode=cloneNode->next; //这个节点找到了找下一个节点 pNode=pNode->next; } return cloneHead; } };

时间复杂度与空间复杂度空间复杂度：
没有用额外的空间O(1)
时间复杂度：
先复制next指针N，在复制random时链表每个节点都要遍历一遍连表N^2
N+N^2 与N^2为等阶无穷大所以最后时间复杂度为O(N^2)
2.方法二：哈希表储存原链表与复制链表的关系(空间换时间) 我们先遍历一遍原链表，将原链表与复制链表的映射关系用mapList储存起来。
这种储存形式类似数组，数组下标为原链表的节点，数组下标的值对应的是复制链表的结点。
我们先遍历原链表，在遍历的时候创建新节点，并建立原节点与新生成的节点的关系
图解连接方法

文章图片

C++代码

/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution {public: RandomListNode* Clone(RandomListNode* pHead) {if(pHead==nullptr) return pHead; mapmapList; RandomListNode*pNode=pHead; while(pNode!=nullptr) {mapList[pNode]=new RandomListNode(pNode->label); //创建新节点，建立原节点与新节点的映射关系 pNode=pNode->next; } pNode=pHead; //链接新链表并通过原新节点的关系来访问原节点的random,来确定新节点的random while(pNode!=nullptr) {mapList[pNode]->next=mapList[pNode->next]; mapList[pNode]->random=mapList[pNode->random]; pNode=pNode->next; } return mapList[pHead]; } };

时间复杂度与空间复杂度空间复杂度：
因为使用了原链表长度的map空间，所以空间复杂度为O(N)
时间复杂度：
一共遍历了两遍数组,2N在N很大时与N为等阶无穷大
所以时间复杂度为O(N)
3.方法三：不把链表分成两份，先复制在拆分链表在方法二上不采用开辟额外空间来保存原链表与复制链表的关系，而是直接在原有链表上进行复制，最后在把原链表拆分为两个链表
【LeetCode|剑指offer_复杂链表的复制(C++_三种方法_时间O(N^2)空间O(1)_复杂问题的拆分 / 时间O(N)空间(N)_哈希表_图解映射 / 时间O(N)空间(1)_链表拆分)】第一步还是复制next节点，但是我们在复制后要连接在原原链表上

文章图片

第二步复制random节点
eg:Arandom指向B,复制后A*random要指向B *,因为链表没有断所以我们找到B *可以通过A->random->next找到B *
第三步拆分链表
把奇数位置上的节点连接起来就是要的复制链表
C++代码

/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution {public: RandomListNode* Clone(RandomListNode* pHead) {CloneNode(pHead); //复制next节点 CloneRandom(pHead); //复制random节点 return SplitNode(pHead); //拆分链表 } void CloneNode(RandomListNode*pHead) {RandomListNode* pNode=pHead; while(pNode!=nullptr) {RandomListNode*clone=new RandomListNode(pNode->label); clone->next=pNode->next; pNode->next=clone; pNode=clone->next; //创建节点，并且将其连接到原链表上 } } void CloneRandom(RandomListNode*pHead) {RandomListNode*pNode=pHead; while(pNode!=nullptr) {RandomListNode*clone=pNode->next; if(pNode->random!=nullptr) {clone->random=pNode->random->next; } //为空不用处理，因为节点构造函数已经将random处理为NULL了 pNode=clone->next; } } RandomListNode*SplitNode(RandomListNode*pHead) {RandomListNode*pNode=pHead; RandomListNode*cloneNode=nullptr; RandomListNode*cloneHead=nullptr; if(pNode!=nullptr) {cloneHead=cloneNode=pNode->next; pNode->next=cloneNode->next; pNode=pNode->next; } while(pNode!=nullptr) {cloneNode->next=pNode->next; cloneNode=cloneNode->next; pNode->next=cloneNode->next; pNode=pNode->next; } return cloneHead; } };

时间复杂度与空间复杂度空间复杂度：
没有使用额外空间，空间复杂度为O(1)
时间复杂度：
一共遍历了三遍数组,3N在N很大时与N为等阶无穷大
所以时间复杂度为O(N)