Clone Linked List with Random Pointer in DSA Rust - Execution Trace

Concept Flow - Clone Linked List with Random Pointer

Start at head of original list

↓

Create new node and insert after original node

↓

Move to next original node

↓

Repeat until end of list

↓

Assign random pointers for new nodes

↓

Separate new nodes to form cloned list

↓

Return head of cloned list

We first insert cloned nodes between original nodes, then assign random pointers, and finally separate the cloned list from the original.

Execution Sample

DSA Rust

fn clone_list(head: Option<Box<Node>>) -> Option<Box<Node>> {
    // Step 1: Insert cloned nodes
    // Step 2: Assign random pointers
    // Step 3: Separate cloned list
}

This code clones a linked list where each node has a random pointer, by interleaving cloned nodes, setting random pointers, and separating the lists.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Insert clone after node 1	1 -> 2 -> null	node1.next = clone1; clone1.next = node2	1 -> 1' -> 2 -> null
2	Insert clone after node 2	1 -> 1' -> 2 -> null	node2.next = clone2; clone2.next = null	1 -> 1' -> 2 -> 2' -> null
3	Assign random pointer for clone1	1 -> 1' -> 2 -> 2' -> null	clone1.random = node1.random.next (clone of node1.random)	1 -> 1'(random->2') -> 2 -> 2' -> null
4	Assign random pointer for clone2	1 -> 1' -> 2 -> 2' -> null	clone2.random = node2.random.next (clone of node2.random)	1 -> 1'(random->2') -> 2 -> 2'(random->1') -> null
5	Separate cloned list	1 -> 1' -> 2 -> 2' -> null	node1.next = node2; clone1.next = clone2; node2.next = null; clone2.next = null	Original: 1 -> 2 -> null; Cloned: 1' -> 2' -> null
6	Return cloned list head	Original and cloned lists separated	Return clone1 as head	Cloned list head at 1'

💡 All original nodes processed, cloned list separated and returned.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
head	1 -> 2 -> null	1 -> 1' -> 2 -> null	1 -> 1' -> 2 -> 2' -> null	1 -> 1' -> 2 -> 2' -> null	1 -> 2 -> null
clone_head	null	null	null	1' -> 2' -> null	1' -> 2' -> null
current	1	2	2	null	null
clone_current	null	1'	2'	null	null

Key Moments - 3 Insights

Why do we insert cloned nodes between original nodes instead of creating a separate list directly?

Inserting clones between original nodes allows easy access to the clone of any node via original.next, which helps assign random pointers correctly as shown in steps 1 and 3 of the execution_table.

How do we assign the random pointer of a cloned node?

We assign clone.random = original.random.next because original.random.next points to the clone of the node that original.random points to, as shown in steps 3 and 4.

Why do we separate the cloned list after assigning random pointers?

Separation restores the original list and extracts the cloned list as independent, preventing interference between the two lists, as shown in step 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the visual state of the list?

A 1 -> 2 -> null

B 1 -> 1' -> 2 -> 2' -> null

C 1' -> 2' -> null

D 1 -> 1' -> null

💡 Hint

Check the 'Visual State' column in step 2 of the execution_table.

At which step do we assign the random pointer for clone2?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Operation' column describing random pointer assignments.

If we skip separating the cloned list, what would be the state after step 5?

A Only cloned nodes remain

B Only original nodes remain

C Original and cloned nodes interleaved

D Random pointers are lost

💡 Hint

Refer to the 'Pointer Changes' and 'Visual State' columns in step 5.

Concept Snapshot

Clone Linked List with Random Pointer:
1. Insert cloned nodes after each original node.
2. Assign cloned nodes' random pointers using original.random.next.
3. Separate cloned nodes to form the cloned list.
This preserves original list and creates a deep copy with random pointers.

Full Transcript

To clone a linked list with random pointers, we first insert cloned nodes right after each original node. This interleaving helps us easily assign the random pointers of cloned nodes by pointing them to original.random.next, which is the clone of the original node's random target. After setting all random pointers, we separate the cloned nodes from the original list to form an independent cloned list. This process ensures the original list remains unchanged and the cloned list is a deep copy with correct next and random pointers.

Practice

1. What is the main challenge when cloning a linked list with a random pointer?

easy

A. Copying the data values of each node

B. Copying the random pointers correctly to the new nodes

C. Reversing the linked list before cloning

D. Sorting the linked list nodes

Solution

1. Step 1: Understand the structure of the linked list

   The linked list has two pointers: next and random. The next pointer points to the next node, and the random pointer can point to any node or null.

2. Step 2: Identify the cloning challenge

   While copying nodes is straightforward, correctly assigning the random pointers in the cloned list is tricky because they can point anywhere in the original list.

3. Final Answer:

   Copying the random pointers correctly to the new nodes -> Option B

4. Quick Check:

   Random pointer cloning = main challenge [OK]

Hint: Focus on random pointer mapping for correct cloning [OK]

Common Mistakes:

• Ignoring random pointers during cloning
• Assuming random pointers follow next pointers
• Copying only data without pointers

2. Which Rust syntax correctly defines a node struct for a linked list with a random pointer?

easy

A. struct Node { val: i32, next: Option, random: Option<*mut Node> }

B. struct Node { val: i32, next: Option, random: Option }

C. struct Node { val: i32, next: Option<Node>, random: Option<Node> }

D. struct Node { val: i32, next: Box<Node>, random: Box<Node> }

Solution

1. Step 1: Understand Rust pointer types for linked lists

   Rust uses Option for owning next nodes. For random pointers, raw pointers (*mut Node) are used to avoid ownership conflicts.

2. Step 2: Analyze each struct definition

   struct Node { val: i32, next: Option, random: Option<*mut Node> } uses Option for next and Option<*mut Node> for random, which is correct. struct Node { val: i32, next: Option, random: Option } wrongly uses Box<Node> for random, causing ownership issues. struct Node { val: i32, next: Option<Node>, random: Option<Node> } uses Node directly, which is invalid. struct Node { val: i32, next: Box<Node>, random: Box<Node> } uses Box<Node> without Option, disallowing null.

3. Final Answer:

   struct Node { val: i32, next: Option, random: Option<*mut Node> } -> Option A

4. Quick Check:

   Correct pointer types = struct Node { val: i32, next: Option, random: Option<*mut Node> } [OK]

Hint: Use Option for next, raw pointer for random [OK]

Common Mistakes:

• Using Box<Node> without Option for nullable pointers
• Using Box<Node> for random causing ownership errors
• Using Node directly instead of Box or pointer

3. Given the following Rust code snippet for cloning a linked list with random pointers, what will be the output printed?

fn print_list(head: &Option) {
    let mut current = head;
    while let Some(node) = current {
        let random_val = match node.random {
            Some(ptr) => unsafe { (*ptr).val },
            None => -1,
        };
        println!("{} -> Random: {}", node.val, random_val);
        current = &node.next;
    }
}

// Original list: 1 -> 2 -> null
// Random pointers: 1.random -> 2, 2.random -> 1
// After cloning, print cloned list using print_list(cloned_head)

medium

A. 1 -> Random: 1
2 -> Random: 2

B. 1 -> Random: -1
2 -> Random: -1

C. 1 -> Random: 2
2 -> Random: 1

D. Compilation error due to unsafe block

Solution

1. Step 1: Understand the print_list function

   The function prints each node's value and the value of the node pointed by its random pointer. If random is None, it prints -1.

2. Step 2: Analyze the original and cloned list random pointers

   Original list has 1.random -> 2 and 2.random -> 1. The cloned list should preserve these random pointer relations, so printing cloned list shows the same pattern.

3. Final Answer:

   1 -> Random: 2 2 -> Random: 1 -> Option C

4. Quick Check:

   Random pointers preserved = output B [OK]

Hint: Random pointers keep same target values after cloning [OK]

Common Mistakes:

• Assuming random pointers reset to self or None
• Confusing node values with random pointer values
• Thinking unsafe block causes compile error

4. In the Rust cloning function below, what is the bug causing incorrect random pointers in the cloned list?

fn clone_list(head: &Option) -> Option {
    let mut map = std::collections::HashMap::new();
    let mut current = head;
    while let Some(node) = current {
        let new_node = Box::new(Node { val: node.val, next: None, random: None });
        map.insert(node as *const _, new_node);
        current = &node.next;
    }
    // Second pass to assign next and random pointers
    // ...
    None
}

medium

A. Not cloning node.val causes wrong values

B. Using raw pointer as key causes runtime error

C. Missing unsafe block around map insertion

D. Inserting Box<Node> into map moves ownership of cloned nodes, preventing proper linking

Solution

1. Step 1: Analyze map insertion of new_node

   Inserting new_node (Box<Node>) into map moves ownership of the cloned node into the HashMap, preventing proper linking of next and random pointers.

2. Step 2: Understand ownership rules in Rust cloning

   To keep original nodes intact, cloned nodes should be stored separately without moving original nodes. The map should store references or pointers, not move ownership.

3. Final Answer:

   Inserting Box<Node> into map moves ownership of cloned nodes, preventing proper linking -> Option D

4. Quick Check:

   Ownership moved incorrectly = bug C [OK]

Hint: Avoid moving ownership when mapping original to cloned nodes [OK]

Common Mistakes:

• Assuming raw pointers cause runtime errors
• Ignoring ownership move semantics
• Forgetting to clone node values

5. You want to clone a linked list with random pointers in Rust without using extra space (no HashMap). Which approach correctly achieves this?

hard

A. Interleave cloned nodes between original nodes, then separate lists

B. Use recursion to clone nodes and random pointers

C. Copy nodes into a vector, then assign random pointers by index

D. Clone nodes and random pointers in a single pass using a stack

Solution

1. Step 1: Understand the interleaving technique

   Insert cloned nodes immediately after original nodes, so each original node points to its clone. This allows setting random pointers by referencing original nodes' random pointers' next nodes.

2. Step 2: Separate the interleaved list into original and cloned lists

   After setting random pointers, detach cloned nodes to form the cloned list, restoring the original list.

3. Final Answer:

   Interleave cloned nodes between original nodes, then separate lists -> Option A

4. Quick Check:

   Interleaving nodes = no extra space cloning [OK]

Hint: Interleave clones to link random pointers without extra space [OK]

Common Mistakes:

• Using recursion causes stack overflow on large lists
• Using vector wastes extra space
• Stack approach is not standard for this problem