剑指Offer35-复杂链表的复制
请实现 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]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
-
-10000 <= Node.val <= 10000
-
Node.random 为空（null）或指向链表中的节点。
-
节点数目不超过 1000 。
来源：力扣（LeetCode）
链接：力扣
一解
本题难点是如何实现 random ，采用哈希表。以 head = [[1,1],[2,1]] 为例：
第一步：在字典 dic 中建立映射：
第二步：根据 node_1 和 node_2 的 next 和 random，构建new node 的 next 和 random。
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return
dic = {}
cur = head
while cur:
dic[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
dic[cur].next = dic.get(cur.next)
dic[cur].random = dic.get(cur.random)
cur = cur.next
return dic[head]
时间复杂度：O(N)
空间复杂度：O(N)
二解
一解属于暴力解法，哈希表浪费空间。
以 head = [[1,1],[2,1]] 为例：
第一步原节点并构造成下述结构：
第二步根据“原node”构造“新node”的 random ，注意下图绿色虚线：
第三步，拆分两个链表：
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head: return
cur = head
while cur:
tmp = Node(cur.val)
tmp.next = cur.next
cur.next = tmp
cur = tmp.next
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
pre = head
cur = res = head.next
while cur.next:
pre.next = pre.next.next
cur.next = cur.next.next
pre = pre.next
cur = cur.next
pre.next = None
return res
return dic[head]
时间复杂度：O(N)
空间复杂度：O(1)