题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

方法1（哈希表法）

左神

思路

创建一个哈希表，存放原始链表的节点和我自己的节点
分成两步走
（1）拷贝原始链表的每一个节点，做成我自己的节点，并通过哈希表进行映射，也就是说原始的pHead，我这里就是m[pHead];这一步不考虑指针问题，就复制一份一模一样的节点
（2）通过哈希表进行补充我自己的链表，我节点的next就是我哈希表里对应的节点的next，random也一样

程序

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        //定义一个map表，映射原始节点和我自己的节点
        unordered_map<RandomListNode*,RandomListNode*> m;
        RandomListNode* p=pHead;
        //从原始链表的头结点开始，复制一份一模一样的节点到映射中，原始节点——我的节点，这个时候不管指针，只复制节点
        while(p!=NULL)
        {
            RandomListNode* temp=new RandomListNode(p->label);
            m.insert(make_pair(p,temp));
            p=p->next;
        }
        //这一步不能忘了，要把指针重新从头开始，开始处理指针了
        p=pHead;
        //m[p]就是我自己的节点，我自己节点的next就是映射表里对应那个的next，直接指过去，random也是一样的
        while(p!=NULL)
        {
            m[p]->next=m[p->next];
            m[p]->random=m[p->random];
            p=p->next;
        }
        //m[pHead]就是我自己的头结点
        return m[pHead];
    }
};

方法二（复制节点挂在原节点后面，再进行分离操作）

思路

把每个节点复制，复制后的点挂在节点后面：1->1'->2->2'->3->3'，然后再进行分离
之后可以再看下书上的讲解思路