Clone Linked List with Random Pointer in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Cloning a Linked List with Random Pointers

What is the printed state of the cloned linked list after running the Rust code below? The list nodes have values and random pointers as shown.

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>>>,
}

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

    // Step 1: Insert cloned nodes
    let mut current = head.clone();
    while let Some(node) = current {
        let cloned = Rc::new(RefCell::new(Node {
            val: node.borrow().val,
            next: node.borrow().next.clone(),
            random: None,
        }));
        node.borrow_mut().next = Some(cloned.clone());
        current = cloned.borrow().next.clone();
    }

    // Step 2: Assign random pointers
    current = head.clone();
    while let Some(node) = current {
        if let Some(random_node) = &node.borrow().random {
            if let Some(cloned_node) = &node.borrow().next {
                cloned_node.borrow_mut().random = random_node.borrow().next.clone();
            }
        }
        if let Some(next_node) = &node.borrow().next {
            current = next_node.borrow().next.clone();
        } else {
            current = None;
        }
    }

    // Step 3: Separate cloned list
    let mut original = head;
    let cloned_head = original.as_ref().unwrap().borrow().next.clone();
    let mut clone_current = cloned_head.clone();

    while let Some(orig_node) = original {
        let cloned_node = orig_node.borrow().next.clone();
        orig_node.borrow_mut().next = cloned_node.as_ref().unwrap().borrow().next.clone();
        if let Some(cloned_node) = cloned_node {
            if let Some(next_orig) = &orig_node.borrow().next {
                cloned_node.borrow_mut().next = next_orig.borrow().next.clone();
            } else {
                cloned_node.borrow_mut().next = None;
            }
        }
        original = orig_node.borrow().next.clone();
    }

    cloned_head
}

fn print_list(head: Option<Rc<RefCell<Node>>>) {
    let mut current = head;
    let mut result = vec![];
    while let Some(node) = current {
        let val = node.borrow().val;
        let random_val = match &node.borrow().random {
            Some(r) => r.borrow().val,
            None => -1,
        };
        result.push(format!("{}(rand->{})", val, random_val));
        current = node.borrow().next.clone();
    }
    println!("{}", result.join(" -> "));
}

fn main() {
    // Create nodes
    let node1 = Rc::new(RefCell::new(Node { val: 1, next: None, random: None }));
    let node2 = Rc::new(RefCell::new(Node { val: 2, next: None, random: None }));
    let node3 = Rc::new(RefCell::new(Node { val: 3, next: None, random: None }));

    // Setup next pointers
    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());

    // Setup random pointers
    node1.borrow_mut().random = Some(node3.clone());
    node2.borrow_mut().random = Some(node1.clone());
    node3.borrow_mut().random = Some(node3.clone());

    let cloned_head = clone_list(Some(node1));
    print_list(cloned_head);
}

A 1(rand->3) -> 2(rand->1) -> 3(rand->3)

B 1(rand->3) -> 2(rand->3) -> 3(rand->1)

C 1(rand->1) -> 2(rand->2) -> 3(rand->3)

D 1(rand->2) -> 2(rand->3) -> 3(rand->1)

💡 Hint

Trace the cloning steps carefully, especially how random pointers are assigned.

The cloned list copies the values and random pointers exactly as the original. Node 1's random points to node 3, node 2's random points to node 1, and node 3's random points to itself.

❓ Predict Output

intermediate

Resulting List Length After Cloning

After cloning a linked list with random pointers using the standard interleaving method, what is the length of the cloned list if the original list has 4 nodes?

DSA Rust

fn count_length(head: Option<std::rc::Rc<std::cell::RefCell<Node>>>) -> usize {
    let mut count = 0;
    let mut current = head;
    while let Some(node) = current {
        count += 1;
        current = node.borrow().next.clone();
    }
    count
}

// Assume clone_list function is correct and returns cloned list head
// Original list length = 4
// cloned_head = clone_list(original_head)
// length = count_length(cloned_head)

A 0

B 5

C 8

D 4

💡 Hint

The cloned list should have the same number of nodes as the original.

The cloning process creates exactly one new node per original node, so the cloned list length equals the original list length.

🔧 Debug

advanced

Identify the Error in Random Pointer Assignment

In the following Rust snippet for cloning a linked list with random pointers, what error will occur during execution?

DSA Rust

while let Some(node) = current {
    if let Some(random_node) = &node.borrow().random {
        if let Some(cloned_node) = &node.borrow().next {
            cloned_node.borrow_mut().random = Some(random_node.clone());
        }
    }
    if let Some(next_node) = &node.borrow().next {
        current = next_node.borrow().next.clone();
    } else {
        current = None;
    }
}

A SyntaxError due to missing semicolon

B The cloned random pointer points to the original node instead of the cloned node

C Runtime panic due to null pointer dereference

D Infinite loop because current is never updated

💡 Hint

Check what is assigned to the cloned node's random pointer.

Assigning cloned_node.borrow_mut().random = Some(random_node.clone()) sets the random pointer to the original node, not the cloned one. The correct assignment should be to the cloned node corresponding to random_node.

🧠 Conceptual

advanced

Why Interleaving Nodes Helps in Cloning Random Pointers

Why does the interleaving method (inserting cloned nodes between original nodes) simplify cloning a linked list with random pointers?

A It allows direct access to the cloned node from the original node, making random pointer assignment easier

B It reduces the total number of nodes, saving memory

C It sorts the list nodes by their values for faster access

D It removes the need for random pointers in the cloned list

💡 Hint

Think about how the cloned node is positioned relative to the original node.

By placing cloned nodes right after their originals, the algorithm can find the cloned node of any original node's random pointer by simply accessing the next node of that random pointer.

🚀 Application

expert

Output After Modifying Cloned List Random Pointers

Given a cloned linked list with nodes 1 -> 2 -> 3, where each node's random pointer points to itself, what is the printed output after setting the random pointer of node 2 to point to node 3?

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>>>,
}

fn print_list(head: Option<Rc<RefCell<Node>>>) {
    let mut current = head;
    let mut result = vec![];
    while let Some(node) = current {
        let val = node.borrow().val;
        let random_val = match &node.borrow().random {
            Some(r) => r.borrow().val,
            None => -1,
        };
        result.push(format!("{}(rand->{})", val, random_val));
        current = node.borrow().next.clone();
    }
    println!("{}", result.join(" -> "));
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { val: 1, next: None, random: None }));
    let node2 = Rc::new(RefCell::new(Node { val: 2, next: None, random: None }));
    let node3 = Rc::new(RefCell::new(Node { val: 3, next: None, random: None }));

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());

    node1.borrow_mut().random = Some(node1.clone());
    node2.borrow_mut().random = Some(node2.clone());
    node3.borrow_mut().random = Some(node3.clone());

    // Change node2's random pointer to node3
    node2.borrow_mut().random = Some(node3.clone());

    print_list(Some(node1));
}

A 1(rand->3) -> 2(rand->3) -> 3(rand->3)

B 1(rand->1) -> 2(rand->2) -> 3(rand->3)

C 1(rand->1) -> 2(rand->3) -> 3(rand->3)

D 1(rand->1) -> 2(rand->1) -> 3(rand->1)

💡 Hint

Focus on the effect of changing node 2's random pointer.

Initially, all random pointers point to themselves. Changing node 2's random pointer to node 3 updates only that node's random pointer.

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