58. Copy List with Random Pointer
Create independent copies of all nodes in the next-linked list, then reproduce both the next relationships and the arbitrary random relationships among the copied nodes.
Copied references must point to copied nodes, never back into the original list. The original node graph must be restored and remain unchanged when the method finishes.
Example 1
Input
N0(7)→N1(7)→N2(9); random=[N2,N1,N2]
Output
Fresh C0→C1→C2; random=[C2,C1,C2]
Explanation: Duplicate values remain distinct identities. Two edges share C2, and C1 retains its self-random relation.
Example 2
Input
N0.next=null, N0.random=N0
Output
C0.next=null, C0.random=C0
Explanation: A self-loop through random is legal; a next self-loop is outside the contract.
Example 3
Input
null
Output
null
Explanation: No nodes allocated and no writes.
Constraints
0 <= nodes per input list <= 105-231 <= node.value <= 231 - 1- The next chain is acyclic. Each random link is null or points within that chain.
Hints
Hint 1
How would an original-to-copy identity map translate a random edge?
Hint 2
Can the copy be placed somewhere reachable directly from its original without a map?
Hint 3
Weave copies, translate random through target.next, then unweave both chains while restoring the source.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Forward, self, and shared random targets
[7,7,9]
[2,1,2]
[{"id":"C0","value":7,"next":"C1","random":"C2"},{"id":"C1","value":7,"next":"C2","random":"C1"},{"id":"C2","value":9,"next":null,"random":"C2"}]