Clone Linked List with Random Pointer in DSA Rust

Mental Model

We want to make a copy of a linked list where each node has two pointers: one to the next node and one to any random node in the list. The challenge is to copy both pointers correctly without mixing original and copied nodes.

Analogy: Imagine you have a chain of people holding hands (next pointer) and each person also points to a random friend in the group (random pointer). Cloning means making a new group with the same hand-holding order and the same random friendships, but with new people.

Original list:
1 -> 2 -> 3 -> null
|    |    |
v    v    v
3    1    2

Here, each node points to the next and also points randomly to another node.

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, random pointers: 1.random -> 3, 2.random -> 1, 3.random -> 2

Goal: Create a new list that is a deep copy of the original, with next and random pointers correctly assigned.

Step 1: Insert cloned nodes after each original node

1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
random pointers unchanged

Why: This interleaving helps link original nodes to their clones directly.

Step 2: Assign random pointers for cloned nodes using original nodes' random pointers

1.random -> 3, 1'.random -> 3'
2.random -> 1, 2'.random -> 1'
3.random -> 2, 3'.random -> 2'

Why: Cloned node's random pointer is set to the clone of the original node's random target.

Step 3: Separate the cloned list from the original list

Original: 1 -> 2 -> 3 -> null
Cloned: 1' -> 2' -> 3' -> null
random pointers preserved in cloned list

Why: We restore the original list and extract the cloned list as a separate copy.

Result:

Cloned list:
1' -> 2' -> 3' -> null
random pointers:
1'.random -> 3'
2'.random -> 1'
3'.random -> 2'

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
    random: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, next: None, random: None }))
    }
}

fn clone_list(head: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
    if head.is_none() {
        return None;
    }

    // Step 1: Insert cloned nodes after original nodes
    let mut curr = head.clone();
    while let Some(node) = curr {
        let next = node.borrow().next.clone();
        let cloned = Node::new(node.borrow().val);
        cloned.borrow_mut().next = next.clone();
        node.borrow_mut().next = Some(cloned);
        curr = next;
    }

    // Step 2: Assign random pointers for cloned nodes
    curr = head.clone();
    while let Some(node) = curr {
        if let Some(random) = node.borrow().random.clone() {
            if let Some(cloned) = node.borrow().next.clone() {
                cloned.borrow_mut().random = random.borrow().next.clone();
            }
        }
        if let Some(next_original) = node.borrow().next.clone() {
            curr = next_original.borrow().next.clone();
        } else {
            curr = None;
        }
    }

    // Step 3: Separate cloned list from original list
    curr = head.clone();
    let cloned_head = head.as_ref().unwrap().borrow().next.clone();
    while let Some(node) = curr {
        let cloned = node.borrow().next.clone();
        let next_original = cloned.as_ref().unwrap().borrow().next.clone();
        node.borrow_mut().next = next_original.clone();
        if let Some(cloned_node) = cloned {
            cloned_node.borrow_mut().next = next_original.as_ref().and_then(|n| n.borrow().next.clone());
        }
        curr = next_original;
    }

    cloned_head
}

fn print_list(head: Option<Rc<RefCell<Node>>>) {
    let mut curr = head;
    while let Some(node) = curr {
        let val = node.borrow().val;
        let random_val = node.borrow().random.as_ref().map_or(-1, |r| r.borrow().val);
        print!("{}(random:{}) -> ", val, random_val);
        curr = node.borrow().next.clone();
    }
    println!("null");
}

fn main() {
    // Create original list 1->2->3
    let n1 = Node::new(1);
    let n2 = Node::new(2);
    let n3 = Node::new(3);
    n1.borrow_mut().next = Some(n2.clone());
    n2.borrow_mut().next = Some(n3.clone());

    // Set random pointers
    n1.borrow_mut().random = Some(n3.clone());
    n2.borrow_mut().random = Some(n1.clone());
    n3.borrow_mut().random = Some(n2.clone());

    println!("Original list:");
    print_list(Some(n1.clone()));

    let cloned = clone_list(Some(n1));

    println!("Cloned list:");
    print_list(cloned);
}

while let Some(node) = curr { let next = node.borrow().next.clone(); let cloned = Node::new(node.borrow().val); cloned.borrow_mut().next = next.clone(); node.borrow_mut().next = Some(cloned); curr = next; }

Insert cloned nodes after each original node to interleave original and clone.

while let Some(node) = curr { if let Some(random) = node.borrow().random.clone() { if let Some(cloned) = node.borrow().next.clone() { cloned.borrow_mut().random = random.borrow().next.clone(); } } if let Some(next_original) = node.borrow().next.clone() { curr = next_original.borrow().next.clone(); } else { curr = None; } }

Assign random pointers for cloned nodes using original nodes' random pointers.

while let Some(node) = curr { let cloned = node.borrow().next.clone(); let next_original = cloned.as_ref().unwrap().borrow().next.clone(); node.borrow_mut().next = next_original.clone(); if let Some(cloned_node) = cloned { cloned_node.borrow_mut().next = next_original.as_ref().and_then(|n| n.borrow().next.clone()); } curr = next_original; }

Separate the cloned list from the original list restoring original next pointers.

Output

Original list:

1(random:3) -> 2(random:1) -> 3(random:2) -> null

Cloned list:

1(random:3) -> 2(random:1) -> 3(random:2) -> null

Complexity Analysis

Time: O(n) because we traverse the list a constant number of times proportional to the number of nodes.

Space: O(1) extra space because we clone nodes in place without using extra data structures for mapping.

vs Alternative: Compared to using a hash map to store original-to-clone mappings which uses O(n) extra space, this approach is more space efficient.

Edge Cases

empty list

returns None immediately without errors

DSA Rust

if head.is_none() { return None; }

single node with random pointer to itself

cloned node's random pointer correctly points to itself

DSA Rust

cloned.borrow_mut().random = random.borrow().next.clone();

random pointers are None

cloned nodes have random pointers set to None

DSA Rust

if let Some(random) = node.borrow().random.clone() { ... }

When to Use This Pattern

When you see a linked list with an extra random pointer and need to clone it, use the interleaving nodes pattern to copy nodes and assign random pointers efficiently.

Common Mistakes

Mistake: Not interleaving cloned nodes with original nodes, causing difficulty in assigning random pointers.
Fix: Insert cloned nodes immediately after original nodes to link clones with originals directly.

Mistake: Assigning random pointers of cloned nodes to original nodes instead of cloned nodes.
Fix: Set cloned node's random pointer to original node's random's next node (the clone).

Mistake: Not restoring the original list's next pointers after cloning.
Fix: Separate the cloned list and restore original next pointers in the final step.

Summary

Creates a deep copy of a linked list where each node has a next and a random pointer.

Use when you need to clone complex linked lists with arbitrary random connections.

Interleave cloned nodes with original nodes to assign random pointers without extra space.

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