Deep Copy a Random-Pointer List
Learn this problem
SuperhumanFULLTIMEPHONE SCREENProblem statement
A linked list has n nodes in next-pointer order. Each node contains an integer value and a random pointer that may target any node or be null.
The list is encoded by nodes, where nodes[i] = [value, randomIndex]. The next pointer of node i targets node i + 1, except for the last node. A randomIndex of -1 means null.
Create a deep copy whose next and random pointers target only copied nodes. For this exercise, after copying, mutate the original node at mutationIndex: set its value to newValue and its random pointer to newRandomIndex.
Return two encoded snapshots in order: the mutated original list, then the unchanged deep copy.
Function
copyAndMutateRandomList(nodes: int[][], mutationIndex: int, newValue: int, newRandomIndex: int) → int[][][]Examples
Example 1
nodes = [[7,-1],[13,0],[11,4],[10,2],[1,0]]mutationIndex = 1newValue = 130newRandomIndex = 4return = [[[7,-1],[130,4],[11,4],[10,2],[1,0]],[[7,-1],[13,0],[11,4],[10,2],[1,0]]]The second original node changes to [130,4]. The second copied node remains [13,0], so the copy is independent.
Example 2
nodes = [[1,1],[2,1]]mutationIndex = 0newValue = 10newRandomIndex = -1return = [[[10,-1],[2,1]],[[1,1],[2,1]]]The first original node loses its random pointer. The copy retains both original random references.
Example 3
nodes = [[5,0]]mutationIndex = 0newValue = 6newRandomIndex = -1return = [[[6,-1]],[[5,0]]]The one-node copy keeps its self-random pointer even after the original is changed.
Constraints
1 <= nodes.length <= 10^4.- Every row of
nodescontains exactly two integers. -10^9 <= nodes[i][0], newValue <= 10^9.- Every random index and
newRandomIndexis-1or an index from0throughnodes.length - 1. 0 <= mutationIndex < nodes.length.