Copy List with Random Pointer - codepath/compsci_guides GitHub Wiki

Unit 12 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Linked Lists, Deep Copy, Pointers

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • How do we create a deep copy of the list?

    • Each node in the copied list must be a completely new object with no references to the original list.

  • What happens if the original list has None pointers?

    • If the input list is empty (head == None), return None.
HAPPY CASE
Input: A linked list: 7 -> 13 -> 11 -> 10 -> 1 with random pointers.
Output: A deep copy of the same structure, where the object ids of nodes differ.

Input: A two-node list: 1 -> 2 with both nodes pointing to 2.
Output: A deep copy of the same structure.

EDGE CASE
Input: An empty list
Output: None

Input: A single node with no random pointer.
Output: A new list with one node and no random pointer.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Copying Linked Lists with Random Pointers, we want to consider the following approaches:

  • Interleaving Nodes: Create new nodes alongside the original nodes to maintain order and manage random pointers.
  • Hash Maps (Alternative): Store original nodes and their copies in a hash map to manage random pointers efficiently (not used here).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
We can solve this problem in three passes:

  1. Create new nodes and place them immediately after the original nodes.
  2. Set the random pointers for the new nodes.
  3. Separate the new list from the original list.
1) Traverse the list and create new nodes interleaved with the original nodes.
2) Set the `random` pointers for the new nodes.
3) Detach the copied list from the original list.
4) Return the head of the copied list.

⚠️ Common Mistakes

  • Forgetting to correctly link the random pointers.
  • Not properly separating the original list from the copied list.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value=0, next=None, random=None):
        self.value = value
        self.next = next
        self.random = random

def copy_random_list(head):
    if not head:
        return None

    # Step 1: Create new nodes and interleave them with the original nodes
    current = head
    while current:
        new_node = Node(current.value, current.next, None)
        current.next = new_node
        current = new_node.next

    # Step 2: Set the random pointers for the new nodes
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next

    # Step 3: Separate the original and copied lists
    current = head
    new_head = head.next
    while current:
        copy = current.next
        current.next = copy.next
        current = current.next
        if copy.next:
            copy.next = copy.next.next

    return new_head

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: A list: 7 -> 13 -> 11 -> 10 -> 1 with interleaving random pointers.

    • After first pass: 7 -> 7' -> 13 -> 13' -> ...
    • After setting random pointers: 7'.random = None, 13'.random = 7', etc.
    • Output: Deep copy with correct values and separate object ids.

  • Input: A list: 1 -> 2, both with random pointers to 2.

    • Output: (1, 2) -> (2, 2)

  • Input: An empty list.

    • Output: None

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the input linked list.

  • Time Complexity: O(N) because we traverse the list three times.
  • Space Complexity: O(1) since no extra space is used beyond the new list.