复杂链表的复制

解题思路

利用字典来将source和duplication的地址对应存储起来，形如

map<RandomListNode*,RandomListNode*> mymap;
mymap[pts] = ptd; // pts代表源地址，ptd代表副本地址。

这样就在原始的链表与副本之间建立了一一对应的关系，那么副本中的节点要想获得下一个节点的地址可以去查看字典

mymap[head2]->next = mymap[head2->next];
mymap[head2]->random = mymap[head2->random];

这样问题就基本上解决了。完整代码：

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(!pHead) return nullptr;
        RandomListNode* head = pHead;
        map<RandomListNode*,RandomListNode*> mymap;
        while(head)
        {
            RandomListNode* cur =  new RandomListNode(head->label);
            mymap[head] = cur;
            head = head->next;
        }
        RandomListNode* head2 = pHead;
        while(head2)
        {
            mymap[head2]->next = mymap[head2->next];
            mymap[head2]->random = mymap[head2->random];
            head2 = head2->next;
        }
        return mymap[pHead];
    }
}; 

时间复杂度：O(2n),空间复杂度：O(n).