前往此题

哈希表法

利用哈希表将链表将节点与节点组成键值对关系储存起来，最后在构建新链表的时候遍历原始链表，将原始链表中各节点的next与random从哈希表中获取。

算法流程

1. 新建哈希表dic
2. 遍历原始链表，新建节点并存入到dic中，键值对关系为(原始节点，新节点)
3. 构建新链表中各节点的next与random的指向

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
      if not head: return None
      cur = head
      dic = {}
      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]

拼接拆分法

通过node1->newnode1->node2->newnode2->node3->newnode3的方式来创建新节点并进行拼接，为的是在接下来构建新链表时能借助旧链表的random节点快速的指向到新链表的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

        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

复杂度分析

时间复杂度： O(N)

空间复杂度： O(1)