复杂链表的复制——容易理解的版本（Cpp实现）

思路

遍历一次旧链表，同时创建新链表的节点，用一个Map保存旧链表和新链表的节点地址对应关系。再遍历一次旧链表，同时根据对应关系给新链表每个节点的next和random成员赋值。
本题一共需要三个辅助指针，一个用来固定指向新链表的头，一个用来遍历旧链表，一个用来遍历新链表。

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

代码

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if (!pHead)
            return NULL;
        RandomListNode* nHead = new RandomListNode(pHead->label); // 用来指向新链表的头
        RandomListNode* po = pHead, *pn = nHead; // po用来遍历旧链表，pn用来遍历新链表

        map<RandomListNode*, RandomListNode*> nodeMap;

        while(po) // 第一次遍历保存新旧节点地址对应关系
        {
            nodeMap[po] = new RandomListNode(po->label);
            po = po->next;
        }
        po = pHead;
        while(po) // 第二次遍历给新链表每个节点的next和random成员赋值。
        {
            pn->next = nodeMap[po->next];
            pn->random = nodeMap[po->random];
            po = po->next;
            pn = pn->next;
        }

        return nHead;
    }
};