How do you solve Copy List with Random Pointer on LeetCode?

Copy List with Random Pointer (LeetCode #138) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding deep copy vs shallow copy is crucial.

What is the brute force solution for Copy List with Random Pointer?

The brute force approach for Copy List with Random Pointer is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves creating a copy of each node and then manually linking the next and random pointers. This is straightforward but inefficient, as it requires multiple passes through the list. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Copy List with Random Pointer?

Copy List with Random Pointer uses the following concepts: Hash Table, Linked List. The recommended patterns to study are: Hash Map, Linked List.

What are the interview tips for Copy List with Random Pointer?

Explain your thought process clearly as you code. Be prepared to discuss edge cases, such as an empty list or a list with only one node. Practice writing clean and efficient code.

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

Failing to handle the case where random pointers point to null. Not separating the original and copied lists correctly.

#138

Copy List with Random Pointer

Medium

Hash TableLinked ListHash MapLinked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a single pass to create interleaved copies of the original nodes and then separates them into two lists. This reduces the number of passes needed and avoids the need for additional space for mapping.

⚙️

Algorithm

3 steps

1Step 1: Create new nodes interleaved with the original nodes.
2Step 2: Set the random pointers for the new nodes based on the original nodes' random pointers.
3Step 3: Separate the interleaved list into the original list and the copied list.

solution.py33 lines

1class Node:
2    def __init__(self, val=0, next=None, random=None):
3        self.val = val
4        self.next = next
5        self.random = random
6
7
8def copyRandomList(head):
9    if not head:
10        return None
11    current = head
12    # Step 1: Create new nodes interleaved with original nodes
13    while current:
14        new_node = Node(current.val)
15        new_node.next = current.next
16        current.next = new_node
17        current = new_node.next
18    # Step 2: Set random pointers
19    current = head
20    while current:
21        if current.random:
22            current.next.random = current.random.next
23        current = current.next.next
24    # Step 3: Separate the lists
25    current = head
26    pseudo_head = Node(0)
27    copy_current = pseudo_head
28    while current:
29        copy_current.next = current.next
30        current.next = current.next.next
31        current = current.next
32        copy_current = copy_current.next
33    return pseudo_head.next

ℹ

Complexity note: This complexity is O(n) because we only traverse the list a constant number of times (three passes), and we do not use any extra space for mapping.

1Understanding deep copy vs shallow copy is crucial.
2Recognizing the need to handle random pointers is key to solving the problem.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.