算法（22）-复制含随机指针的单链表-C++

单链表结构如下：两个节点 对象指针。
 

class Noderand
{
public:
    int m_value;
    Noderand * next;
    Noderand * rand;
    Noderand(int value);

};
Noderand::Noderand(int value)
{
    m_value = value;
}

思路：用hashMap key-value  老、新节点。
           1.遍历一次生成map 从左到右
            2.再遍历一次        从左到右
上代码

class NodeRandom {
public:
    int value;
    NodeRandom *next;
    NodeRandom *rand;
     NodeRandom(int data) {
        value = data;
    }
};
NodeRandom* copyListWithRand(NodeRandom *head) 
{
    unordered_map<NodeRandom*, NodeRandom*> map;
    NodeRandom *cur = head;
    while (cur !=NULL)                            //1.遍历生成哈希表
    {
        map.insert(make_pair(cur, new NodeRandom(cur->value)));
        cur = cur->next;
    }
    cur = head;
    while (cur != NULL)                          //2.再遍历一遍，重新赋值 赋值的是 NodeRandom* 类型
    {
        map.find(cur) = map.find(cur->next); //哈希表查找
        map.find(cur) = map.find(cur->rand);
        cur = cur->next;
    }
    return map.find(head)->first;
}

void printRandLinkedList(NodeRandom* head) 
{
    NodeRandom *cur = head;
    cout<<"order: "<<endl;
    while (cur!= NULL) {
        cout << cur->value<<",";
        cur = cur->next;
    }
    cout << endl;
    cur = head;
    cout << "rand:  " << endl;
    while (cur != NULL) 
    {
        if(cur->rand == NULL)
        {
            cout << "-,";
        }
        else
        {
            cout << cur->rand->value<<",";
        }
        cur = cur->next;
    }
    cout << endl;
}

void CopyListWithRandom_test()
{
    NodeRandom* head = NULL;
    NodeRandom* res1 = NULL;


    head = new NodeRandom(1);
    head->next = new NodeRandom(2);
    head->next->next = new NodeRandom(3);
    head->next->next->next = new NodeRandom(4);
    head->next->next->next->next = new NodeRandom(5);
    head->next->next->next->next->next = new NodeRandom(6);

    head->rand = head->next->next->next->next->next; // 1 -> 6
    head->next->rand = head->next->next->next->next->next; // 2 -> 6
    head->next->next->rand = head->next->next->next->next; // 3 -> 5
    head->next->next->next->rand = head->next->next; // 4 -> 3
    head->next->next->next->next->rand = NULL; // 5 -> null
    head->next->next->next->next->next->rand = head->next->next->next; // 6 -> 4


    printRandLinkedList(head);
    res1 = copyListWithRand(head);
    cout<<"*************"<<endl;
    printRandLinkedList(res1);
}
void CopyListWithRandom_main()
{
    cout<<"*****CopyListWithRandom_main********"<<endl;
    CopyListWithRandom_test();

}