Copy List with Random Pointer
A linked list is given where each node contains:
- val — an integer value
- next — a pointer to the next node
- random — a pointer to any node in the list or null
Construct a deep copy of the linked list.
The copied list must contain completely new nodes, while preserving the same next and random relationships as the original list.
Example 1
Input
5 7 13 11 10 1 -1 0 4 2 0
Output
7 13 11 10 1
Explanation
The copied list contains the same values and preserves all random pointer relationships, but every node is a newly created node.
Example 2
Input
2 1 2 1 1
Output
1 2
Explanation
Both nodes in the copied list preserve their random pointers, pointing to the copied node corresponding to the original target.
Constraints
Hints:
Hint 1
Create a mapping from every original node to its corresponding copied node.
Hint 2
Traverse the original list and create a new node for every original node.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 10, 2026
Last updated
Aug 11, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output