解题思路：

1、利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可
2、考虑构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。
具体步骤：
复制各节点，构建拼接链表:设原链表为 node1→node2→⋯ ，构建的拼接链表如下所示：
                        node1→node1_new→node2→node2_new →
构建新链表各节点的 random 指向：当访问原节点 cur 的随机指向节点 cur.random 时，对应新节点 cur.next 的随机指向节点为 cur.random.next 。
拆分原 / 新链表：设置 pre / cur 分别指向原 / 新链表头节点，遍历执行 pre.next = pre.next.next 和 cur.next = cur.next.next 将两链表拆分开。
返回新链表的头节点 res 即可。
举例说明：
复杂链表：{1,2,3,4,5,3,5,#,2,#}
（1）初始化哈希表dict，节点cur指向头节点
（2）复制链表；建立新节点，循环遍历链表，并向 dict 添加键值对 (原 cur 节点, 新 cur 节点）
（3）构建新链表的引用指向；cur遍历原链表，构建新节点的next、random引用指向
（4）返回新链表的头节点 dict[pHead]

图解：


代码:

Python版本: 
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        # 利用字典保存新旧链表节点的对应关系
        dict = {}
        cur = pHead
        # 建立新的链表节点 字典
        while cur:
            dict[cur] = RandomListNode(cur.label)
            cur = cur.next
        # 建立新节点的关联字典
                cur = pHead
        while cur:
            dict[cur].next = dict.get(cur.next)
            dict[cur].random = dict.get(cur.random)
            cur = cur.next
        return dict[pHead]
JAVA版本： 
import java.util.Map;
import java.util.HashMap;
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if(pHead == null) return null;
        RandomListNode cur = pHead;
        Map<randomlistnode> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(pHead);
    }
}</randomlistnode>

复杂度分析：

时间复杂度 O(N)： 两轮遍历链表，使用 O(N) 时间。
空间复杂度 O(N) ： 哈希表 dict 使用线性大小的额外空间