LeetCode-Copy List with Random Pointer

题目：

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

1. You must return the copy of the given head as a reference to the cloned list.

解题1：

       节点中存在随机节点， 由于是随机节点指向下一个节点的随机性， 拷贝时建议next与random新老地址的映射关系。实现1：建立hash表创建关系，拷贝后next和random都从hash表中获取对应的拷贝值的地址即可。

实现1：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(NULL == head){
            return nullptr;
        }
        unordered_map<Node*, Node*>m;
        Node *cur = head;
        while (cur != nullptr){
            Node *node = new Node(cur->val, nullptr, nullptr);
            m[cur] = node;
            cur = cur->next;
        }
        cur = head;
        while(cur != nullptr){
            m[cur]->next = m[cur->next];
            m[cur]->random = m[cur->random];
            cur = cur->next;
        }
        return m[head];
           
    }
};

Runtime: 40 ms
Memory Usage: 22.4 MB
时间复杂度O(n)， 空间复杂度O(n)

解题2：

       递归方式判断hash表中是否存在映射关系， 存在返回， 否则复制节点并建立映射关系，之后按照同样方式处理next和random

实现2：

class Solution {
    
public:
    unordered_map<Node*, Node*>m;
    Node* copyRandomList(Node* head) {
        if(NULL == head){
            return nullptr;
        }
        if(m.find(head)!= m.end()){
            return m[head];
        }
        Node *node = new Node(head->val, nullptr, nullptr);
        if (NULL == node){
            return nullptr;
        }
        m[head] = node;
        node->next = copyRandomList(head->next);
        node->random = copyRandomList(head->random);
        return node;
           
    }
};
Runtime: 28 ms
Memory Usage: 22.6 MB
时间复杂度O(n)， 空间复杂度O(n)

解题3：

       复制链表节点，放入当前节点后；遍历复制节点，赋值新节点的random，新节点random所指向节点，就是原有节点random所指节点的next （新节点拷贝了原有节点后）；断开链接返回拷贝后的节点。

实现3：

class Solution {
    
public:
    
    Node* copyRandomList(Node* head) {
        if(NULL == head){
            return nullptr;
        }
        //copy
        Node *cur=head;
        while(cur){
            Node *node = new Node(cur->val, nullptr, nullptr);
            node->next = cur->next;
            cur->next = node;
            cur=node->next;
        }
        
        //set random
        cur=head;
        while(cur){
            if (cur->random){
                cur->next->random = cur->random->next;
            }
            cur=cur->next->next;
        }
       
        //ret copy link
        cur = head;
        Node *res=head->next;
        while(cur){
            Node *copy = cur->next;
            cur->next = copy->next;
            if (copy->next) {
                copy->next = copy->next->next;
            }
            cur=cur->next;
        }
        return res;
           
    }
};

Runtime: 28 ms
Memory Usage: 22.2 MB
时间复杂度O(n)， 空间复杂度O(1)

方法三在第一步复制链表， 将新节点插入原有链表，先修改了原有链表的导致Memory Limit Exceeded， 修改链表时要注意修改顺序， 针对本地要先将修改要插入的节点再修改原有链表上的节点。

参考：

Java-O(n)-solution   

C++ simple recursive solution

A solution with constant space complexity O(1) and linear time complexity O(N)