JZ35-题解 | #复杂链表的复制#
复杂链表的复制
http://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针random指向一个随机节点),请对此链表进行深拷贝,并返回拷贝后的头结点。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针,虚线箭头表示random指针。为简单起见,指向null的指针没有画出。
题解1:
采用先深拷贝各个节点,然后random重新指向,最后拆分链表
1、将深拷贝的节点插入在被拷贝节点的后面
2、改变深拷贝的节点的random指针指向
3、将原链表共和新链表拆开
图示引自牛客500979850号
代码
struct RandomListNode {
int label;
struct RandomListNode* next, * random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
RandomListNode* Clone(RandomListNode* pHead) {
if (!pHead) return NULL;
//链表的深拷贝,把深拷贝的节点插在下一个节点处
RandomListNode* cur = pHead;
while (cur) { // 深拷贝所有的节点,并重新排序
RandomListNode* temp = new RandomListNode(cur->label);//创建新节点并复制节点内容
temp->next = cur->next;//将新结点插入在cur结点的下一个结点
cur->next = temp;
//重新连接之后,cur指针指向原来的下一个节点
cur = temp->next;
}
//当原来的节点存在random时候,构造新的random
cur = pHead;
while (cur) {
if (cur->random) {//当B->random指向A时候(画图理解)如:A->A'->B->B'->C->C'-NULL
cur->next->random = //那么B->next->random就指向A'
cur->random->next;//A'就是B->random->next
}
//移动cur指向原节点的下一个指针
cur = cur->next->next;
}
//将原链表和拷贝链表进行拆分
//新建一个虚拟头节点
RandomListNode* myhead = new RandomListNode(-1);
myhead->next = pHead->next;
cur = pHead;
// while(cur->next){
// RandomListNode * temp = cur->next;
// cur->next = temp->next;
// cur = temp;
// }
//上面注释代码是对每个节点进行重新指向,也可采用下面的方式
while (cur) {
RandomListNode* temp = cur->next;
if (cur->next) cur->next = temp->next;
cur = cur->next;//移动指针
if (temp->next) temp->next = cur->next;
//注意:不用移动temp,循环体的开头已经移动了temp指针了
}
return myhead->next;
}
题解2:使用无需map方式
图示引自:Maokt
代码
RandomListNode* Clone(RandomListNode* pHead) {
if (!pHead) return NULL;
//创建map,其中key是老节点,value是新节点
unordered_map<RandomListNode*, RandomListNode*> map;//无顺序的map
RandomListNode* old = pHead;
RandomListNode* myhead = new RandomListNode(-1);//新链表头节点
RandomListNode* m_temp = myhead;
while (old) {
RandomListNode* temp = new RandomListNode(old->label);
m_temp->next = temp;//创建新链表之后,将之插入
m_temp = m_temp->next;
map[old] = temp;//将新老节点放入map中
old = old->next;//移动指向老链表的指针
}
for (unordered_map<RandomListNode*, RandomListNode*>::iterator it = map.begin(); it != map.end(); it++) {
if ((*it).first->random)//(*it).first是老节点,(*it).second是新节点
(*it).second->random = map[(*it).first->random];
else
(*it).second->random == NULL;
}
//for (auto& [key,value]:map) {//对map进行遍历
// value->random = key->random ? map[key->random] : NULL;
// //map[key, value]中,key为老链表节点,value为新链表节点(也是key的深拷贝节点)
// // map[key->random]的value就是key->random指向老节点的深拷贝节点
//}
return myhead->next;
}