文章目录
1.方法一：复杂问题的拆分
这种思路非常的简到直白，就是将复杂问题拆分开。先复制next节点，最后再复制随机节点random
注意：
1.在复制随机节点random时，因为这个节点指向的未知是随机的，所以每次找random指向的节点时要从头节点开始找起。
2.random指针可能为空指针，在写代码时要进行判断
定义两个节点指针，一个指向原链表的头节点s，另一个指向复制的链表的头节点sc，讲pNode这个位置的random保存起来tmp。当s!=tmp时说明还没有找到这个节点的random，s向下移动，sc向下移动。当s==tmp时表明sc也找到了复制链表这个节点的random指针
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;
map<RandomListNode*,RandomListNode*>mapList;
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.方法三：不把链表分成两份，先复制在拆分链表
在方法二上不采用开辟额外空间来保存原链表与复制链表的关系，而是直接在原有链表上进行复制，最后在把原链表拆分为两个链表
第一步还是复制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)