/**

* Definition for a Node.

* public class Node {

* public var val: Int

* public var next: Node?

* public var random: Node?

* public init(_ val: Int) {

* self.val = val

* self.next = nil

* self.random = nil

* }

* }

*/

// Cache of mapping from old to new nodes

func copyRandomList(_ head:Node?)->Node?{

// Base case: Nil node

guardlet node= headelse{returnnil}

// Mapping exists

guardmapping[node]==nilelse{returnmapping[node]!}

// Create new node

letnewNode=Node(node.val)

// Add to cache (i.e. 'visit' this node)

mapping[node]= newNode

// Recursive calls (preorder -> children calls)

newNode.next=copyRandomList(node.next)

newNode.random=copyRandomList(node.random)

return newNode