#138

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Copy List with Random Pointer

This problem requires copying a linked list where each node has a random pointer in addition to the next pointer.

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Hash Table

We can define a dummy head node $\textit{dummy}$ and use a pointer $\textit{tail}$ to point to the dummy head node. Then, we traverse the linked list, copying each node and storing the mapping between each node and its copy in a hash table $\textit{d}$, while also connecting the $\textit{next}$ pointers of the copied nodes.

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        d = {}
        dummy = tail = Node(0)
        cur = head
        while cur:
            node = Node(cur.val)
            tail.next = node
            tail = tail.next
            d[cur] = node
            cur = cur.next
        cur = head
        while cur:
            d[cur].random = d[cur.random] if cur.random else None
            cur = cur.next
        return dummy.next

Solution 2: Simulation (Space Optimization)

In Solution 1, we used an additional hash table to store the mapping between the original nodes and the copied nodes. We can also achieve this without using extra space, as follows:

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        d = {}
        dummy = tail = Node(0)
        cur = head
        while cur:
            node = Node(cur.val)
            tail.next = node
            tail = tail.next
            d[cur] = node
            cur = cur.next
        cur = head
        while cur:
            d[cur].random = d[cur.random] if cur.random else None
            cur = cur.next
        return dummy.next

Continue Practicing

#141 linked list cycle #142 linked list cycle ii #146 lru cache