题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针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;
}