Copy List with Random Pointer — Medium Coding Interview Question

A linked list of length n has each node containing an extra random pointer, which could point to any node in the list or null. Construct a deep copy of the list. The list is given as an array of [val, randomindex] pairs (randomindex is null if the random pointer is null). Return the deep copy encoded the same way.

Example

Input: pairs = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Constraints

• 0 ≤ n ≤ 1000
• -10⁴ ≤ Node.val ≤ 10⁴

Topics & Companies

Topics: linked-list, hash-map

Asked by: Amazon, Google, Meta, Microsoft, Bloomberg

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns