剑指 Offer 35. 复杂链表的复制

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
/*
*   思想是，使用哈希表将旧的节点映射到新的节点上，可以使用map
*   如果头结点为空，则直接返回。
*   不为空，先遍历旧的链表，做一一映射
*   再遍历链表，对random进行赋值
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL){
            return NULL;
        }
        Node * cur = head;
        map<Node*,Node*> mp;
        //做一一映射 
        while(cur !=NULL){
            mp[cur] = new Node(cur->val);
            cur = cur->next;
        }
        //对cur要重新赋值,这个地方在第一次提交的时候忘记了
        cur = head;
        //对next 和 random进行赋值
        while(cur !=NULL){
            mp[cur]->next = mp[cur->next];
            mp[cur]->random = mp[cur->random];
            cur = cur->next;
        }
        return mp[head];
    }
};