What is the optimal time complexity of solving Copy List With Random Pointer?

The optimized solution achieves a time complexity of O(n) by using sorting, mathematical shortcuts, or hash table lookups.

What is the auxiliary space complexity for Copy List With Random Pointer?

The space complexity is O(1) since we only use a minimal/constant amount of extra memory for tracking variables (or auxiliary space if dynamic structures are allocated).

What are the typical edge cases we must handle in Copy List With Random Pointer?

Key edge cases include empty collections, negative or large bounds causing integer overflow, arrays with only one element, or inputs where target criteria are not met.

How can we optimize the brute force approach for Copy List With Random Pointer?

Brute force methods often inspect all possible combinations. We optimize this by sorting the input list to enable binary search, or tracking processed items in a set to avoid redundant nested loop lookups.

Back to Practice Dashboard

Top 150 InterviewEasy

Copy List With Random Pointer

Learn how to solve the 'Copy List With Random Pointer' problem. This detailed resource details brute force and optimized approaches.

Mode Selected

Problem Statement

Easy

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.

The list is represented as a list of pairs [val, random_index] where random_index is the index of the node the random pointer points to, or -1 if it points to null. Implement a function copyRandomList(head: list) -> list that returns the deep copy in the same format.

Constraints

•0 <= n <= 1000
•-10000 <= Node.val <= 10000
•Node.random is null or points to some node in the linked list

Examples

Example 1

Input

[[7,-1],[13,0],[11,4],[10,2],[1,0]]

Output

[[7,-1],[13,0],[11,4],[10,2],[1,0]]

Explanation

The deep copy has the same structure. Node 0 (val=7) has random=null, Node 1 (val=13) has random pointing to Node 0, etc.

Example 2

Input

[[1,1],[2,1]]

Output

[[1,1],[2,1]]

Explanation

Node 0 (val=1) has random pointing to Node 1. Node 1 (val=2) has random pointing to Node 1 (itself).

Example 3

Input

[[3,-1],[3,0],[3,-1]]

Output

[[3,-1],[3,0],[3,-1]]

Explanation

Three nodes all with value 3. Node 1's random points to Node 0.

Need a Hint?

Analyze the input constraints. Try sorting first (O(n log n)) or using a hash map/set to track seen elements in O(n) time.

Edge Cases to Watch

Empty list or null input variables
Single item lists/arrays
Extremely large input bounds causing integer or stack overflow

Ready to Solve?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

Open in Editor