LeetCode 138. 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.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index]  where:

• val: an integer representing Node.val 
• random_index: the index of the node (range from 0  to n-1) where random pointer points to, or null  if it does not point to any node.

解析：

实现深拷贝链表，每个链表节点包含3个元素，分别是节点值，指向下一个的指针，指向随机元素的指针。对于next指针，在复制节点的时候，同时保留前一个节点指针，复制完当前节点后，上一个节点的next正好指向当前这个节点；难点在于random指针的复制。可以采用HashMap的形式，建立原始节点和复制节点的映射关系。首先遍历一遍链表，复制节点，建立映射；然后在遍历一遍链表，为random指针赋值。具体代码如下：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)
            return NULL;
        Node* res = new Node(head->val, NULL, NULL);//新链表节点
        Node* node = res, *cur = head->next;//原始链表下一个元素
        unordered_map<Node*, Node*> nodes_map;//映射关系
        nodes_map[head] = res;
        while(cur)//第1次遍历 建立映射关系
        {
            Node *temp = new Node(cur->val, NULL, NULL);
            node->next = temp;//前一个节点next指针指向刚复制的节点
            nodes_map[cur] = temp;
            node = node->next;
            cur = cur->next;
        }
        node = res, cur = head;
        while(cur)//第2次遍历 为random赋值
        {
            node->random = nodes_map[cur->random];
            node = node->next;
            cur = cur->next;
        }
        return res;
    }
};