Copy List with Random Pointer

Problem Statement

Given a linked list with a random pointer, create a deep copy of the list. The random pointer is a reference to a node that is randomly chosen from the linked list.

Rules and Constraints

• The linked list is represented as a graph, with each node having a reference to its next node and a random node.
• The input linked list may contain duplicate nodes.
• The output should be a completely separate copy of the input linked list, with no references to the original list.
• Time complexity: O(N), where N is the number of nodes in the linked list.
• Space complexity: O(N), where N is the number of nodes in the linked list.
• Nodes are represented as instances of a Node class with int val, Node next, and Node random attributes.

Note that the random node may be the same node or a different node. However, each node in the original list will only have one random pointer. The random pointer of a node can point to any node in the linked list, including itself.

Example

Input: {"head":"[[7,null],[13,0],[11,4],[10,2],[1,0]]"} Output: "deepCopy"