指针的深拷贝。
来回用两次map即可在nlogn的时间复杂度下解决该问题。

class Solution {
public:
    RandomListNode <em>copyRandomList(RandomListNode *head) {
        int length = getRandomList(head);<br />
        if(length == 0)
            return NULL;
        int index = 0;
        RandomListNode * headb1 = head;
        map&lt;RandomListNode</em>,int&gt;map_ri;
        map_ri.clear();
        while(head != NULL) {
            map_ri.insert(map&lt;RandomListNode<em>,int&gt;::value_type(head,index++));
            head = head-&gt;next;
        }
        int *pos = new int[length];
        map&lt;RandomListNode</em>,int&gt;::iterator itri;
        index = 0;
        head = headb1;
        while(head != NULL) {
            itri = map_ri.find(head-&gt;random);
            if(itri == map_ri.end())
                pos[index++] = -1;
            else
                pos[index++] = itri-&gt;second;
            head = head-&gt;next;
        }
        head = headb1;
        map&lt;int,RandomListNode <em>&gt;map_r;
        map_r.clear();
        index = 0;
        RandomListNode *copy = new RandomListNode(head-&gt;label);
        RandomListNode *copymove = copy;
        map_r.insert(map&lt;int,RandomListNode</em>&gt;::value_type(index++,copymove));
        head = head-&gt;next;
        while(head!=NULL) {
            RandomListNode * tmp = new RandomListNode(head-&gt;label);
            copymove-&gt;next = tmp;
            copymove = copymove-&gt;next;
            map_r.insert(map&lt;int,RandomListNode<em>&gt;::value_type(index++,copymove));
            head=head-&gt;next;
        }
        copymove = copy;
        index = 0;
        while(copymove != NULL) {
            map&lt;int,RandomListNode</em>&gt;::iterator it = map_r.find(pos[index++]);
            if(it == map_r.end())
                copymove-&gt;random = NULL;
            else
                copymove -&gt;random = it-&gt;second;
            copymove = copymove-&gt;next;
        }
        return copy;
    }
private:
    int getRandomList(RandomListNode *head) {
        int length = 0;
        while(head != NULL) {
            head = head-&gt;next;
            length++;
        }
        return length;
    }
};