[编程题]复杂链表的复制

# 774个回答

```class Solution {
public:
/*
1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
2、遍历链表，A1->random = A->random->next;
3、将链表拆分成原链表和复制后的链表
*/

{
while(currNode){
RandomListNode *node = new RandomListNode(currNode->label);
node->next = currNode->next;
currNode->next = node;
currNode = node->next;
}
while(currNode){
RandomListNode *node = currNode->next;
if(currNode->random){
node->random = currNode->random->next;
}
currNode = node->next;
}
//拆分
RandomListNode *tmp;
while(currNode->next){
tmp = currNode->next;
currNode->next =tmp->next;
currNode = tmp;
}
}
};```

```/*
*解题思路：
*1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
*2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
*3、拆分链表，将链表拆分为原链表和复制后的链表
*/
public class Solution {
return null;
}

//1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
while(currentNode != null){
RandomListNode cloneNode = new RandomListNode(currentNode.label);
RandomListNode nextNode = currentNode.next;
currentNode.next = cloneNode;
cloneNode.next = nextNode;
currentNode = nextNode;
}

//2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
while(currentNode != null) {
currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
currentNode = currentNode.next.next;
}

//3、拆分链表，将链表拆分为原链表和复制后的链表
while(currentNode != null) {
RandomListNode cloneNode = currentNode.next;
currentNode.next = cloneNode.next;
cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
currentNode = currentNode.next;
}

}
}```

```public class Solution {
return null;
//复制next 如原来是A->B->C 变成A->A'->B->B'->C->C'
while(pCur!=null){
RandomListNode node = new RandomListNode(pCur.label);
node.next = pCur.next;
pCur.next = node;
pCur = node.next;
}
//复制random pCur是原来链表的结点 pCur.next是复制pCur的结点
while(pCur!=null){
if(pCur.random!=null)
pCur.next.random = pCur.random.next;
pCur = pCur.next.next;
}
//拆分链表
while(pCur!=null){
pCur.next = pCur.next.next;
if(cur.next!=null)
cur.next = cur.next.next;
cur = cur.next;
pCur = pCur.next;
}
}
}```

1、递归法

```/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/

/*递归思想：把大问题转化若干子问题
此题转化为一个头结点和除去头结点剩余部分，剩余部分操作和原问题一致
*/
class Solution {
public:
{
return NULL;

//开辟一个新节点

//递归其他节点

}
};```

2、 三步

```/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
//复制原始链表的任一节点N并创建新节点N'，再把N'链接到N的后边
{
while(pNode!=NULL)
{
RandomListNode* pCloned=new RandomListNode(0);
pCloned->label=pNode->label;
pCloned->next=pNode->next;
pCloned->random=NULL;

pNode->next=pCloned;

pNode=pCloned->next;
}
}
//如果原始链表上的节点N的random指向S，则对应的复制节点N'的random指向S的下一个节点S'
{
while(pNode!=NULL)
{
RandomListNode* pCloned=pNode->next;
if(pNode->random!=NULL)
pCloned->random=pNode->random->next;
pNode=pCloned->next;
}
}
//把得到的链表拆成两个链表，奇数位置上的结点组成原始链表，偶数位置上的结点组成复制出来的链表
{
RandomListNode* pClonedNode=NULL;

//初始化
if(pNode!=NULL)
{
pNode->next=pClonedNode->next;
pNode=pNode->next;

}
//循环
while(pNode!=NULL)
{
pClonedNode->next=pNode->next;
pClonedNode=pClonedNode->next;
pNode->next=pClonedNode->next;
pNode=pNode->next;
}

}
//三步合一
{
}
};```

3、哈希表法

```/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
{
return NULL;

//定义一个哈希表
unordered_multimap<RandomListNode*,RandomListNode*> table;

// 开辟一个头结点

// 将头结点放入map中

//设置操作指针

// 第一遍先将简单链表复制一下
while(pNode!=NULL)
{
// 不断开辟pNode的拷贝结点
RandomListNode* pClonedTail=new RandomListNode(pNode->label);
pClonedTail->next=NULL;
pClonedTail->random=NULL;

//连接新节点，更新当前节点
pClonedNode->next=pClonedTail;
pClonedNode=pClonedTail;

//将对应关系  插入到哈希表中
table.insert(make_pair(pNode,pClonedTail));

//向后移动操作节点
pNode=pNode->next;
}

//需从头开始设置random节点，设置操作指针

// 根据map中保存的数据，找到对应的节点
while(pNode!=NULL)
{

if(pNode->random!=NULL)
{
//找到对应节点，更新复制链表
pClonedNode->random=table.find(pNode->random)->second;
}

//向后移动操作节点
pNode=pNode->next;
pClonedNode=pClonedNode->next;
}

}
};```

1. 把复制的结点链接在原始链表的每一对应结点后面

2. 把复制的结点的random指针指向被复制结点的random指针的下一个结点

3. 拆分成两个链表，奇数位置为原链表，偶数位置为复制链表，注意复制链表的最后一个结点的next指针不能跟原链表指向同一个空结点None，next指针要重新赋值None(判定程序会认定你没有完成复制）

```# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
# 返回 RandomListNode
return None

# first step, N' to N next
while dummy:
dummynext = dummy.next
copynode = RandomListNode(dummy.label)
copynode.next = dummynext
dummy.next = copynode
dummy = dummynext

# second step, random' to random'
while dummy:
dummyrandom = dummy.random
copynode = dummy.next
if dummyrandom:
copynode.random = dummyrandom.next
dummy = copynode.next

# third step, split linked list
while dummy:
copyNode = dummy.next
dummynext = copyNode.next
dummy.next = dummynext
if dummynext:
copyNode.next = dummynext.next
else:
copyNode.next = None
dummy = dummynext

```

```/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;
public class Solution {
{
HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
RandomListNode q = new RandomListNode(-1);
while(p!=null){
RandomListNode t = new RandomListNode(p.label);
map.put(p, t);
p = p.next;
q.next = t;
q = t;
}
Set<Entry<RandomListNode,RandomListNode>> set = map.entrySet();
Iterator<Entry<RandomListNode,RandomListNode>> it = set.iterator();
while(it.hasNext()){
Entry<RandomListNode, RandomListNode> next = it.next();
next.getValue().random = map.get(next.getKey().random);
}
}
}

```

首先遍历一遍原链表，创建新链表（赋值label和next），用map关联对应结点；再遍历一遍，更新新链表的random指针。（注意map中应有NULL ----> NULL的映射）

创建新链表的时候，用原结点的next指针指向对应新结点，新结点的next指针指向下一个原结点，以此类推，形成之字形关联。然后，就可以先更新新链表的random指针，再解除next关联，更新next指针。这种方法不需要map来辅助，不管查找next还是random指针都是O(1)的，效率很高。

```class Solution {
public:
{

map<RandomListNode*,RandomListNode*> m;
}

}
}
};```

```class Solution {
public:
{

// 上链，使新旧链表成之字形链接

// next
}

// 更新新链表的random指针

}

// 脱链，更新各链表的next指针

}

}
};```

# python两种解法

## 递归法：

``````class Solution:
return newNode
``````

## 哈希表法：

``````class Solution:
nodeList = []     #存放各个节点
randomList = []   #存放各个节点指向的random节点。没有则为None
labelList = []    #存放各个节点的值

#random节点的索引，如果没有则为1
labelIndexList = map(lambda c: nodeList.index(c) if c else -1, randomList)

dummy = RandomListNode(0)
pre = dummy
#节点列表，只要把这些节点的random设置好，顺序串起来就ok了。
nodeList=map(lambda c:RandomListNode(c),labelList)
#把每个节点的random绑定好，根据对应的index来绑定
for i in range(len(nodeList)):
if labelIndexList[i]!=-1:
nodeList[i].random=nodeList[labelIndexList[i]]
for i in nodeList:
pre.next=i
pre=pre.next
return dummy.next
``````

```class Solution {
map<RandomListNode*, RandomListNode*> mp;
set<RandomListNode*> vis;
void dfs1(RandomListNode* u){
if(u && mp.find(u) == mp.end()) {
mp[u] = new RandomListNode(u -> label);
dfs1(u -> next);
dfs1(u -> random);
}
}
void dfs2(RandomListNode* u){
if(u && vis.find(u) == vis.end()){
if(u -> next) mp[u] -> next = mp[u -> next];
if(u -> random) mp[u] -> random = mp[u -> random];
vis.insert(u);
dfs2(u -> next);
dfs2(u -> random);
}
}
public:
mp.clear();
vis.clear();
}
};```

JAVA使用哈希表，时间复杂度O(N)，额外空间复杂度O(N)
```import java.util.HashMap;
public class Solution {
{
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
while (cur != null) {
map.put(cur, new RandomListNode(cur.label));
cur = cur.next;
}
while (cur != null) {
map.get(cur).next = map.get(cur.next);
cur = cur.next;
}
while (cur != null) {
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
}
}
```

```public class Solution {
{
if (pHead == null) return null;

return newNode;
}
}```

```public class Solution {
{
if (pHead == null) return null;

while (pCur != null)
{
RandomListNode node = new RandomListNode(pCur.label);
node.next = pCur.next;
pCur.next = node;
pCur = node.next;
}

while (pCur!=null)
{
if (pCur.random!=null)
pCur.next.random = pCur.random.next;
pCur = pCur.next.next;
}

while(pCur.next!=null)
{
tmp = pCur.next;
pCur.next = tmp.next;
pCur = tmp;
}
}
}```

1.利用空间节省时间（引入hashmap，然后在查找random的时候就可以直接从hashmap中查找对应的节点）时间复杂度O(n)。
```
/*

public class RandomListNode {

int label;

RandomListNode next = null;

RandomListNode random = null;

RandomListNode(int label) {

this.label = label;

}

}

*/

importjava.util.HashMap;

publicclassSolution {

{

HashMap<RandomListNode, RandomListNode> map = newHashMap<RandomListNode, RandomListNode>();

map.put(pre, newPre);

while(pre.next != null){

newPre.next = newRandomListNode(pre.next.label);

pre = pre.next;

newPre = newPre.next;

map.put(pre, newPre);

}

while(newPre != null){

newPre.random = map.get(pre.random);

pre = pre.next;

newPre = newPre.next;

}

}

}

```
2.如何在不利用hashmap的情况下，实现O(n)的算法

```public class Solution {
{

//复制节点，并放在源节点之后
while(node != null ){
RandomListNode newNode = new RandomListNode(node.label);
newNode.label = node.label;
newNode.next = node.next;
newNode.random = null;
node.next = newNode;
node = newNode.next;
}
//复制random指向复制后的节点
while(node != null){
RandomListNode newNode = node.next;
if(node.random != null){
newNode.random = node.random.next;
}
node = newNode.next;
}
//获取新的链表
RandomListNode cloneNode = null;
if(pNode != null){
cloneNode = pNode.next;
pNode.next =  cloneNode.next;
pNode = pNode.next;
}

while(pNode != null){
cloneNode.next = pNode.next;
cloneNode = cloneNode.next;
pNode.next = cloneNode.next;
pNode = pNode.next;
}
}

}```

1. 复制单链表
1.1. p指向头结点，只要p不为空，就一直循环；
1.2. 创建新节点，值和p相同；
1.3. 将新节点插入p节点之后；
2. 连接random域
2.1. p指向头结点；
2.2. 将含有random的p节点的后继节点添加random域；
PS：有些节点本身就没有random，再访问random的后继就会出现空指针！
3. 拆分单链表
3.1. p指向头结点，依次向后移动；
3.2. 将p指向后继的后继；
3.3. p的后继指向p的后继的后继的后继；
PS：若p已经为最后一个元素，则p的后继直接为null，否则出现空指针！

```//C++实现 时间效率O(n) 空间效率为0 最优解法
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
{
}

//把每一个节点的复制后的节点，连接在每一个后面
{
while(pNode!=nullptr)
{
//构造函数，新开辟空间用于存复制的节点，由于后面没有赋节点给pCloneNode的步骤，所以不能赋值为nullptr
RandomListNode* pCloneNode=new RandomListNode(0);//label初始化为0
pCloneNode->label=pNode->label;//此步复制了节点
pCloneNode->next=pNode->next;
pCloneNode->random=nullptr;

pNode->next=pCloneNode;
pNode=pCloneNode->next;
}
}

//设置复制出来的节点的random指针
{
while(pNode!=nullptr)
{
RandomListNode* pCloneNode=pNode->next;
if(pNode->random!=nullptr)
pCloneNode->random=pNode->random->next;
pNode=pCloneNode->next;
}
}

//将一个链表拆分为两个链表,并只返回复制的那个链表
{
RandomListNode* pCloneNode=nullptr;

if(pNode!=nullptr)
{
pCloneNode=pNode->next;
pNode->next=pCloneNode->next;//A->B连接
pNode=pCloneNode->next;//把B赋给pNode
}
while(pNode!=nullptr)
{
pCloneNode->next=pNode->next;//A'->B'连接
pCloneNode=pNode->next;//把B‘赋给pCloneNode

pNode->next=pCloneNode->next;//B->C连接 等
pNode=pCloneNode->next;//把C赋给pNode 等
}
}
};```

```//利用C++中的map,虽然空间效率有浪费
//思路简单
class Solution {
public:
{

while(p2->next){
p1->next = new RandomListNode(p2->next->label);
p2 = p2->next; p1 = p1->next;
}

map<RandomListNode *, RandomListNode *>  my_Map;
my_Map[NULL] = NULL;
while(p1 && p2){
my_Map[p2] = p1;
p1 = p1->next; p2 = p2->next;
}

while(p1 && p2){
p1->random = my_Map[p2->random];
p1 = p1->next; p2 = p2->next;
}

}
};```

```/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
{
while(current!=NULL){
RandomListNode* node = new RandomListNode(current->label);
node->next  = current->next;
current->next = node;
current = node->next;//处理下一个节点
}

//处理random指针
while(current!=NULL){
if(current->random!=NULL)
current->next->random = current->random->next;
current = current->next->next;
}

//生成复制链表

while(current!=NULL){
current->next = current->next->next;
if(temp->next!=NULL)
temp->next    = temp->next->next;
temp = temp->next;
current = current->next;
}
}
};

```

## 我的答案

```/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
{
//0.判断空的情况
return null;
}

//1.复制结点
while(node != null){
//保存下一个结点next-->新建一个克隆结点-->指定node.next到克隆结点
//-->克隆结点的next指向next结点-->更新node为next结点
RandomListNode next = node.next;
RandomListNode cloneNode = new RandomListNode(node.label);
node.next = cloneNode;
cloneNode.next = next;
node = next;
}

//2.复制随机引用
while(node != null){
if(node.random != null){
node.next.random = node.random.next;
}
node = node.next.next;
}

//3.分离两个链表
//记录复制的链表的头结点
while(node != null){
RandomListNode currNode = node.next;
//更新原结点的next
node.next = currNode.next;
//更新克隆结点的next
if(currNode.next != null){
currNode.next = currNode.next.next;
}
//更新原结点指针
node = node.next;
}

}
}```

```class Solution {
public:
{
return NULL;
unordered_map<RandomListNode*, RandomListNode*> M;
M[p] = new RandomListNode(p->label);

{
M[p]->next = M[p->next];
M[p]->random = M[p->random];
}
}
};
```

```/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
{
while(curNode!=NULL){
RandomListNode* newNode = new RandomListNode(curNode->label);
newNode->next = curNode->next;
curNode->next = newNode;
curNode = newNode->next;
}
while(curNode!=NULL){
if(curNode->random!=NULL)
curNode->next->random = curNode->random->next;
curNode = curNode->next->next;
}
while(curNode->next!=NULL){
RandomListNode* pNext = curNode->next;
curNode->next = pNext->next;
curNode = pNext;
}
}
};```

``` public RandomListNode Clone(RandomListNode pHead)
{
return null;

while (t != null) {
RandomListNode p = t.next;
RandomListNode r = new RandomListNode(t.label); // copy next
t.next = r;
r.next = p;
t = p;
}

RandomListNode r = t.next;
while (t != null) {
if (t.random != null)
r.random = t.random.next;// copy random
t = r.next;
if (t == null)
break;
r = t.next;
}

r = t.next;
while (t != null) {
t.next = r.next;
t = r.next;

if (t == null)
break;
r.next = t.next;
r = t.next;
}

}```

```public RandomListNode Clone(RandomListNode pHead)
{
while (pNode != null) {
int val = pNode.label;
RandomListNode randomListNode = new RandomListNode(val);
randomListNode.next = pNode.next;
pNode.next = randomListNode;
pNode = randomListNode.next;
}
while (pNode != null) {
RandomListNode next = pNode.next;
RandomListNode random = pNode.random;
if (random != null)
next.random = random.next;
pNode = next.next;
}
while (pNode != null) {
RandomListNode next = pNode.next;
pNode.next = next.next;
pNode = next.next;
if (pNode != null)
next.next = pNode.next;
}
return second;
}
```

774条回答 73348浏览

# 通过挑战的用户

• 2019-05-23 12:48:43
• 2019-05-23 12:11:42
• 2019-05-23 11:55:54
• 2019-05-23 11:45:09
• 2019-05-23 11:39:53

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题