剑指offer 复杂链表的复制
- 题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
- 题目解析
这道题目的难点在于如何解决这个随机指针的复制问题，也就是说在复制的时候如何能够快速找到随机指针指向的节点并且指向它。这里用unordered_map来将原始链表中的结点和复制的结点构成键值对，这样在查找的时候就能很快找到。
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
RandomListNode* dummyHead = new RandomListNode(0);
RandomListNode* p = pHead, *q = dummyHead;
unordered_map<RandomListNode *, RandomListNode*>map;
while (p!=NULL){
q->next = new RandomListNode(p->label);
map.insert(make_pair(p, q->next));
p = p->next;
q = q->next;
}
p = pHead;
q = dummyHead;
while (p!=NULL){
q->next->random = map[p->random];
p = p->next;
q = q->next;
}
return dummyHead->next;
}
};