138. Copy List with Random Pointer

Practice Copy List with Random Pointer for free on NudgeCode: Medium, Linked List pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Every node of a linked list has a val, a next pointer, and a random pointer that points to any node in the list or is null. Return a deep copy of the list: new nodes with the same values, where each copy's next and random point to the copies of the matching nodes.

No pointer in the copy may point to a node of the original list. Returning original nodes, or copies whose random still points into the original list, fails the test.

In the tests a list is written as [[val, random_index], ...]: one pair per node from head to tail, where random_index is the 0-based position of the node that random points to, or null.

Example

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]  ->  [[7,null],[13,0],[11,4],[10,2],[1,0]]

Constraints

• 0 <= number of nodes <= 1000
• -10^4 <= Node.val <= 10^4
• random is null or points to a node in the list