复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

版本一: 克隆每个节点, 并在被克隆的节点之口插入该克隆结点, 被克隆节点与克隆节点相邻, 并且克隆节点的random指针位置正好在被克隆节点random指针的下一位置, 这样刚好可以通过被克隆节点的random指针指向克隆节点random指针的位置

class Solution {public:        void cloneNodes(RandomListNode* pHead) {        while (NULL != pHead) {            RandomListNode *ct = new RandomListNode(pHead->label);            //ct->label = pHead->label;            // 插入            ct->next = pHead->next;            pHead->next = ct;            // pHead指针下移            pHead = ct->next;        }    }        void connectRandomNode(RandomListNode* pHead) {        RandomListNode *pCloneNode = NULL;        while (NULL != pHead) {            // newHead指向克隆出来的节点, 是pHead下一节点            pCloneNode = pHead->next;            // newHead的random指向pHead的random下一节点            if (NULL != pHead->random) {                pCloneNode->random = pHead->random->next;            }            // pHead越过克隆节点, 指向克隆节点的下一节点            pHead = pCloneNode->next;        }    }        RandomListNode* retCloneList(RandomListNode* pHead) {        RandomListNode *pNode = pHead;        RandomListNode *pCloneHead = nullptr;        RandomListNode *pCloneNode = nullptr;        if (nullptr != pHead) {            pCloneHead = pCloneNode = pNode->next;            pNode->next = pCloneNode->next;            pNode = pNode->next;        }        while (nullptr != pNode) {            pCloneNode->next = pNode->next;            pCloneNode = pCloneNode->next;                        pNode->next = pCloneNode->next;            pNode = pNode->next;        }        return pCloneHead;    }        RandomListNode* Clone(RandomListNode* pHead)    {        cloneNodes(pHead);        connectRandomNode(pHead);        return retCloneList(pHead);    }};

版本二: 使用哈希表, 第一次使用哈希表, 简单讲解一下(可能不定对哈), 首先简历一张哈希表, 把源接点与克隆节点插入表中, 哈希表关键字为源节点的地址, 然后遍历哈希表, 通过表中关键字把克隆节点的next与random指针赋值

class Solution {public:    RandomListNode* Clone(RandomListNode* pHead) {        if (pHead == nullptr) {            return nullptr;        }        std::unordered_map
    
      hash_map;        for (RandomListNode* p = pHead; p != nullptr; p = p->next) {            hash_map[p] = new RandomListNode(p->label);        }        for (RandomListNode* p = pHead; p != nullptr; p = p->next)        {            hash_map[p]->next = hash_map[p->next];            hash_map[p]->random = hash_map[p->random];        }        return hash_map[pHead];    }};
    

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