请实现copyRandomList函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。

示例1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

提示：

• -10000 <= Node.val <= 10000
• Node.random为空(null)或指向链表中的节点。
• 节点数目不超过1000。

注意：本题与主站138题相同。

解题思路：

普通链表的节点定义如下：

# Definition for a Node:
class Node:
	def __init__(self, x, next):
		self.val = int(x)
		self.next = next

本题链表的节点定义如下：

# Definition for a Node.
class Node:
	def __init__(self, x, next, random):
	self.val = int(x)
	self.next = next
	self.random = random

给定链表的头节点head，复制普通链表很简单，只需遍历链表，每轮建立新节点+构建前驱节点和当前节点node的引用指向即可。

本题链表的节点新增了random指针，指向链表的任意节点或者null。这个random指针意味着在复制过程中，除了构建前驱节点和当前节点的引用指向pre.next，还要构建前驱节点和其随机节点的引用指向pre.random。

本题难点：在复制链表的过程中构建新链表各节点的random引用指向。

class Solution:
    def copyRandomList(self, head):
        cur = head
        dum = pre = Node(0)
        while cur:
            node = Node(cur.val)# 复制节点cur
            pre.next = node
            # pre.random = "???"
            cur = cur.next
            pre = node
        return dum.next

本文介绍哈希表，拼接+拆分两种方法。哈希表方法比较直观；拼接+拆分方法的空间复杂度更低。

方法一：哈希表

利用哈希表的查询特点，考虑构建原链表节点和新链表对应节点的键值对映射关系，再遍历构建新链表各节点的next和random引用指向即可。

算法流程：

1. 若头节点head为空节点，直接返回null;
2. 初始化：哈希表dic，节点cur指向头节点；
3. 复制链表：
   1. 建立新节点，并向dic添加键值对(原cur节点，新cur节点)；
   2. cur遍历至原链表下一节点；
4. 构建新链表的引用指向：
   1. 构建新节点的next和random引用指向；
   2. cur遍历至原链表下一节点；
5. 返回值：新链表的头节点dic[cur];

复杂度分析：

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

class Solution:
    def copyRandomList(self, head):
        if not head: return
        dic = {}
        # 3.复制各节点，并建立原节点->新节点的Map映射
        cur = head
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        # 4.构建新节点的next和random指向
        while cur:
            dic[cur].next = dic.get(cur.next)
            dic[cur].random = dic.get(cur.random)
            cur = cur.next
         # 5.返回新链表的头节点
        return dic[head]

方法二：拼接+拆分

考虑构建原节点1->新节点1->原节点2->新节点2->…的拼接链表，如此便可在访问原节点的random指向节点的同时找到新对应新节点的random指向节点。

算法流程：

1. 复制各节点，构建拼接链表：

   设原链表为node1->node2->…，构建的拼接链表如下所示：

   node1->node1new->node2->node2new->…

2. 构建新链表各节点的random指向：

   当访问原节点cur的随机指向节点cur.random时，对应新节点cur.next的随机指向节点为cur.random.next。

3. 拆分原/新链表：

   设置pre/cur分别指向原/新链表头节点，遍历执行pre.next=pre.next.next和cur.next = cur.next.next将两链表拆分开。

4. 返回新链表的头节点res即可。

复杂度分析：

• 时间复杂度O(N):三轮遍历链表，使用O(N)时间。
• 空间复杂度O(1):节点引用变量使用常数大小的额外空间。

class Solution:
	def copyRandomList(self, head):
		if not head: return
		cur = head
        # 1.复制各节点，并构建拼接链表
        while cur:
            temp = Node(cur.val)
            temp.next = cur.next
            cur.next = temp
            cur = temp.next
        # 2.构建各新节点的random指向
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3.拆分两链表
        cur = res = head.next
        pre = head
        while cur.next:
            pre.next = pre.next.next
            cur.next = cur.next.next
            pre = pre.next
            cur = cur.next
        pre.next = None
        return res

"""
# Definition for a Node.
class Node:
	def __init__(self, x, next):
		self.val = int(x)
		self.next = next
		self.random = random
"""
class Solution:
    def copyRandomList(self, head):