复杂链表的复制
题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的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<RandomListNode*, RandomListNode*> 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) {
}
};