前往此题

解题思路

如果按照平常的链表，直接按照遍历顺序创建新链表即可，但本题链表存在随机指针，在第一次遍历的时候随机指针还未出现，所以我们需要通过回溯的方式先将该链表中的随机指针生成出来。接下来问题就是如何确定旧节点对应哪个新节点？我们需要通过哈希表，在回溯前将旧节点以key的方式存储在哈希表中，将对应的新节点以value的方式存储在哈希表中，最后返回哈希表中第一个节点即可。

"""
# 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':
        hs = dict()

        def copyRandom(node):
            if not node: return None
            if node not in hs:
                newNode = Node(node.val)
                hs[node] = newNode
                newNode.next = copyRandom(node.next)
                newNode.random = copyRandom(node.random)
            return hs[node]
        return copyRandom(head)