Copy List With Random Pointer Leetcode Problem 138 [Python Solution]

In this tutorial, we discuss and solve a linked list challenge, Copy List With Random Pointer LeetCode problem.

This problem falls under the category of Linked List and is rated as a medium difficulty problem.

It’s a great exercise to improve your understanding of data structures and algorithmic thinking.

Problem Overview

Imagine you have a linked list of length n, where each node not only points to the next node but also contains an additional pointer called random.

This random pointer can point to any node in the list, including null.

Your task is to create a deep copy of this linked list.

The deep copy should consist of n brand new nodes, with each new node having the same value as its corresponding original node.

Both the next and random pointers 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.

None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes, X and Y, in the original list, and X.random points to Y, then for the corresponding two nodes, x and y, in the copied list, x.random should point to y.

The linked list is represented in the input/output as a list of n nodes, each represented as a pair of [val, random_index] where:

• val: an integer representing Node.val.
• random_index: the index of the node (ranging from 0 to n-1) that the random pointer points to or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example:

Input:

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

Output:

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

Input:

head = [[1, 1], [2, 1]]

Output:

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

Input:

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

Output:

[[3, null], [3, 0], [3, null]]

Constraints:

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

Now that we understand the problem, let’s go through the solution step by step.

Efficient Python Code Solution

def copyRandomList(self, head: 'Node') -> 'Node':
    oldToCopy = {None: None}

    cur = head
    while cur:
        copy = Node(cur.val)
        oldToCopy[cur] = copy
        cur = cur.next
    cur = head
    while cur:
        copy = oldToCopy[cur]
        copy.next = oldToCopy[cur.next]
        copy.random = oldToCopy[cur.random]
        cur = cur.next
    return oldToCopy[head]

This Python code provides an efficient solution to the Copy List With Random Pointer problem.

We’ll break down the solution into several components.

Problem Overview

In this problem, we are given a linked list with two types of pointers: next and random.

The goal is to create a deep copy of this linked list while maintaining the relationships between nodes.

We’ll achieve this using a two-pass approach.

Understanding the Algorithm

1. We’ll create a dictionary called oldToCopy to map original nodes to their corresponding copies.

The dictionary will initially have an entry for None mapped to None.

2. In the first pass, we iterate through the original linked list (head) while creating a deep copy of each node.

For each node, we create a new node with the same value and store it in the oldToCopy dictionary, mapping the original node to its copy.

This pass is responsible for creating the copied nodes without connecting the pointers.

3. In the second pass, we iterate through the original linked list again.

For each node, we retrieve its copy from the oldToCopy dictionary.

We then update the next and random pointers of the copy node by looking up the corresponding nodes in the dictionary.

This step connects the next and random pointers for the copied nodes.

4. Finally, we return the head of the copied linked list, which can be obtained from the oldToCopy dictionary by using the original head as the key.

Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list.

This is because we iterate through the list twice, and the dictionary operations are typically O(1).

The space complexity is also O(n) because we use the oldToCopy dictionary to store copies of the nodes, and in the worst case, it will have n entries, one for each node in the linked list.

#

Related Interview Questions By Company:

• Merge Intervals LeetCode
• Network Delay Time LeetCode
• Accounts Merge LeetCode

Related Interview Questions By Difficulty:

• Design Browser History LeetCode
• Swap Nodes In Pairs LeetCode
• Design Linked List LeetCode

Related Interview Questions By Category:

• Delete Node In A BST LeetCode
• Longest Common Prefix LeetCode
• Counting Bits LeetCode

Reasoning Behind Our Efficient Approach

This efficient approach uses a two-pass algorithm and a dictionary to map original nodes to their copies.

The key insights are as follows:

1. We create a deep copy of each node during the first pass, but we don’t connect the pointers (i.e., next and random) at this stage.

Instead, we focus on building the structure of the copied list.

2. During the second pass, we use the oldToCopy dictionary to easily retrieve the corresponding copy for each original node.

This allows us to connect the next and random pointers efficiently.

3. The use of a dictionary (hash map) eliminates the need for additional searching or traversal, making the algorithm run in linear time.

This efficient approach guarantees that we create a true deep copy of the linked list while maintaining the relationships between nodes.

In conclusion, the Copy List With Random Pointer problem can be solved efficiently using a two-pass algorithm and a dictionary to map original nodes to their copies.

For a more detailed explanation and the full code, you can refer to the Python solution provided above.

I hope you found this guide helpful and informative.

If you have any questions, suggestions, or comments, please feel free to share them in the comment section below.

Question Link: Copy List With Random Pointer LeetCode Problem

If you found this content useful, don’t forget to like and engage for more coding tutorials and algorithm explanations.

Your support is greatly appreciated!