How to Solve Copy List with Random Pointer

The Copy List with Random Pointer problem asks you to create a deep copy of a linked list with random pointers. You need to ensure that each node in the copied list has both the next and random pointers properly set, maintaining the structure of the original list. A common approach is to iterate over the list and create new nodes while mapping them using a hash table to handle random pointer references.

Problem Statement

You are given a linked list where each node contains a value and two pointers: a next pointer and a random pointer. The random pointer can point to any node in the list, or it can be null. The task is to create a deep copy of this list, where each node in the copied list should have a new value and new pointers, but the structure should mirror the original linked list, including the random pointer connections.

For example, if node X's random pointer in the original list points to node Y, the corresponding node x in the copied list should have its random pointer point to node y, which is a new node with the same value as node Y. The new list should not share any nodes with the original list, ensuring that all nodes are distinct.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: head = [[1,1],[2,1]]

Output: [[1,1],[2,1]]

Example details omitted.

Example 3

Input: head = [[3,null],[3,0],[3,null]]

Output: [[3,null],[3,0],[3,null]]

Example details omitted.

Constraints

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

Solution Approach

Iterative with Hash Map

Create a hash map to store the mapping between original nodes and their corresponding copied nodes. Then, iterate through the list once, creating new nodes, and store them in the hash map. Afterward, use the hash map to set the random pointers in the copied list.

Constant Space with Node Duplication

You can avoid extra space by modifying the original list itself. First, iterate through the list and insert a copy of each node directly after the original. Then, assign the random pointers for the copied nodes. Finally, separate the original and copied lists.

Optimized with Two Pointers

Using two pointers, first iterate through the list to copy each node and insert them next to their corresponding original nodes. Then, go through the list again to fix the random pointers, and finally, separate the two lists.

Complexity Analysis

The time complexity of the iterative approach with a hash map is O(n), where n is the number of nodes, as we iterate through the list twice. The space complexity is also O(n) due to the hash map. The constant space approach reduces the space complexity to O(1), but it still requires O(n) time for the initial and final iterations.

What Interviewers Usually Probe

• Candidate understands how to handle linked list pointers effectively.
• The candidate uses efficient space management in their solution.
• The solution works for lists with random pointers pointing to multiple nodes.

Common Pitfalls or Variants

Common pitfalls

• Failing to correctly manage the random pointers, especially in cases where they point to null.
• Not properly separating the original and copied lists, leading to shared nodes.
• Overcomplicating the solution with unnecessary space usage, like excessive use of additional data structures.

Follow-up variants

• Handle the case where the input list is empty.
• Extend the problem by allowing more complex random pointer relationships, such as multiple nodes referencing the same random node.
• Modify the problem to work with doubly linked lists, where each node has both next and previous pointers in addition to random pointers.

How GhostInterview Helps

• GhostInterview provides step-by-step guidance for solving problems like Copy List with Random Pointer, helping you efficiently manage linked list pointers.
• The tool helps you visualize and optimize your approach, whether you're using a hash map, constant space, or two pointers.
• GhostInterview ensures your solution is robust by highlighting common pitfalls such as pointer mismanagement or node sharing in the copied list.

Topic Pages

• Hash Table
• Linked List

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

How can I solve the Copy List with Random Pointer problem efficiently?

You can solve the problem using either a hash map to map original nodes to new nodes or by iterating through the list and inserting copies next to original nodes to minimize space usage.

What is the best space-efficient solution for Copy List with Random Pointer?

The best space-efficient solution involves modifying the original list directly, where you insert copied nodes next to the original nodes and then separate the lists.

What are the common mistakes when solving Copy List with Random Pointer?

Common mistakes include incorrectly handling random pointers, not separating original and copied lists, and using unnecessary extra space.

Can I solve Copy List with Random Pointer using recursion?

Yes, you can solve the problem recursively by first creating deep copies of the nodes, but this might introduce extra space usage due to recursion stack.

How does GhostInterview help with Copy List with Random Pointer?

GhostInterview offers a clear approach to solve Copy List with Random Pointer, from step-by-step guidance to checking your solution against potential pitfalls and optimizations.