Delete a Node from Circular Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after deleting a node from circular linked list

What is the printed state of the circular linked list after deleting the node with value 3?

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

impl Node {
    fn new(data: i32) -> Self {
        Node { data, next: None }
    }
}

fn delete_node(head: &mut Option<Box<Node>>, key: i32) {
    if head.is_none() {
        return;
    }
    let mut curr = head.as_mut().unwrap();
    let mut prev: Option<&mut Box<Node>> = None;
    loop {
        if curr.data == key {
            if let Some(p) = prev {
                p.next = curr.next.take();
            } else {
                // Deleting head node
                if curr.next.is_none() {
                    *head = None;
                } else {
                    let mut tail = curr.next.as_mut().unwrap();
                    while tail.next.is_some() && tail.next.as_ref().unwrap().data != curr.data {
                        tail = tail.next.as_mut().unwrap();
                    }
                    *head = curr.next.take();
                    tail.next = head.clone();
                }
            }
            break;
        }
        if curr.next.is_none() {
            break;
        }
        prev = Some(curr);
        curr = curr.next.as_mut().unwrap();
    }
}

fn print_list(head: &Option<Box<Node>>) {
    if head.is_none() {
        println!("null");
        return;
    }
    let mut curr = head.as_ref();
    let start = curr.unwrap().data;
    loop {
        print!("{} -> ", curr.unwrap().data);
        curr = curr.unwrap().next.as_ref();
        if curr.is_none() || curr.unwrap().data == start {
            break;
        }
    }
    println!("null");
}

fn main() {
    let mut head = Some(Box::new(Node::new(1)));
    head.as_mut().unwrap().next = Some(Box::new(Node::new(2)));
    head.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new(3)));
    head.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = head.clone();

    delete_node(&mut head, 3);
    print_list(&head);
}

A 1 -> 2 -> 3 -> null

B 1 -> 2 -> null

C 2 -> 3 -> null

D 1 -> null

💡 Hint

Think about how the node with value 3 is removed and how the links are updated.

After deleting node 3, the list contains nodes 1 and 2 linked circularly. The print function stops after printing 2 because the next node is the start node 1 again.

❓ Predict Output

intermediate

Output after deleting the head node in circular linked list

What is the printed state of the circular linked list after deleting the node with value 1 (head node)?

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

impl Node {
    fn new(data: i32) -> Self {
        Node { data, next: None }
    }
}

fn delete_node(head: &mut Option<Box<Node>>, key: i32) {
    if head.is_none() {
        return;
    }
    let mut curr = head.as_mut().unwrap();
    let mut prev: Option<&mut Box<Node>> = None;
    loop {
        if curr.data == key {
            if let Some(p) = prev {
                p.next = curr.next.take();
            } else {
                // Deleting head node
                if curr.next.is_none() {
                    *head = None;
                } else {
                    let mut tail = curr.next.as_mut().unwrap();
                    while tail.next.is_some() && tail.next.as_ref().unwrap().data != curr.data {
                        tail = tail.next.as_mut().unwrap();
                    }
                    *head = curr.next.take();
                    tail.next = head.clone();
                }
            }
            break;
        }
        if curr.next.is_none() {
            break;
        }
        prev = Some(curr);
        curr = curr.next.as_mut().unwrap();
    }
}

fn print_list(head: &Option<Box<Node>>) {
    if head.is_none() {
        println!("null");
        return;
    }
    let mut curr = head.as_ref();
    let start = curr.unwrap().data;
    loop {
        print!("{} -> ", curr.unwrap().data);
        curr = curr.unwrap().next.as_ref();
        if curr.is_none() || curr.unwrap().data == start {
            break;
        }
    }
    println!("null");
}

fn main() {
    let mut head = Some(Box::new(Node::new(1)));
    head.as_mut().unwrap().next = Some(Box::new(Node::new(2)));
    head.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new(3)));
    head.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = head.clone();

    delete_node(&mut head, 1);
    print_list(&head);
}

A 2 -> 3 -> null

B 1 -> 2 -> 3 -> null

C 3 -> 2 -> null

D null

💡 Hint

Deleting the head means the new head is the next node.

After deleting node 1, the head moves to node 2. The circular link is updated so 3 points back to 2.

🔧 Debug

advanced

Identify the error in circular linked list deletion code

What error will this Rust code produce when trying to delete a node from a circular linked list?

DSA Rust

fn delete_node(head: &mut Option<Box<Node>>, key: i32) {
    let mut curr = head.as_mut().unwrap();
    while curr.data != key {
        curr = curr.next.as_mut().unwrap();
    }
    curr = curr.next.take();
}

A panic at unwrap on None when key not found

B compiles and deletes node correctly

C infinite loop without deleting node

D syntax error due to missing semicolon

💡 Hint

Consider what happens if the key is not in the list.

If the key is not found, unwrap on None will panic causing runtime error.

🧠 Conceptual

advanced

Why is special handling needed when deleting the head node in circular linked list?

Why must we handle deletion of the head node differently in a circular linked list?

A Because the head node is the only node with a pointer to itself

B Because circular linked list does not have a head node

C Because head node cannot be deleted in circular linked list

D Because the tail node's next pointer must be updated to new head

💡 Hint

Think about the circular link from tail to head.

When deleting head, tail's next pointer must point to new head to maintain circularity.

🚀 Application

expert

Resulting list after multiple deletions in circular linked list

Given a circular linked list with nodes 1 -> 2 -> 3 -> 4 -> (back to 1), what is the printed list after deleting nodes 2 and 4 in order?

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

impl Node {
    fn new(data: i32) -> Self {
        Node { data, next: None }
    }
}

fn delete_node(head: &mut Option<Box<Node>>, key: i32) {
    if head.is_none() {
        return;
    }
    let mut curr = head.as_mut().unwrap();
    let mut prev: Option<&mut Box<Node>> = None;
    loop {
        if curr.data == key {
            if let Some(p) = prev {
                p.next = curr.next.take();
            } else {
                if curr.next.is_none() {
                    *head = None;
                } else {
                    let mut tail = curr.next.as_mut().unwrap();
                    while tail.next.is_some() && tail.next.as_ref().unwrap().data != curr.data {
                        tail = tail.next.as_mut().unwrap();
                    }
                    *head = curr.next.take();
                    tail.next = head.clone();
                }
            }
            break;
        }
        if curr.next.is_none() {
            break;
        }
        prev = Some(curr);
        curr = curr.next.as_mut().unwrap();
    }
}

fn print_list(head: &Option<Box<Node>>) {
    if head.is_none() {
        println!("null");
        return;
    }
    let mut curr = head.as_ref();
    let start = curr.unwrap().data;
    loop {
        print!("{} -> ", curr.unwrap().data);
        curr = curr.unwrap().next.as_ref();
        if curr.is_none() || curr.unwrap().data == start {
            break;
        }
    }
    println!("null");
}

fn main() {
    let mut head = Some(Box::new(Node::new(1)));
    head.as_mut().unwrap().next = Some(Box::new(Node::new(2)));
    head.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new(3)));
    head.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new(4)));
    head.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = head.clone();

    delete_node(&mut head, 2);
    delete_node(&mut head, 4);
    print_list(&head);
}

A null

B 1 -> 2 -> 3 -> 4 -> null

C 1 -> 3 -> null

D 3 -> 1 -> null

💡 Hint

Delete nodes one by one and update links carefully.

After deleting 2 and 4, only nodes 1 and 3 remain linked circularly.

Practice

1. What happens when you delete the only node in a circular linked list?

easy

A. The list points to itself indefinitely.

B. The list still contains the deleted node.

C. The list becomes empty (null).

D. The list throws an error.

Solution

1. Step 1: Understand the structure of a single-node circular linked list

   In a circular linked list with one node, the node's next pointer points to itself.

2. Step 2: Delete the only node

   Removing this node means no nodes remain, so the list becomes empty (null).

3. Final Answer:

   The list becomes empty (null). -> Option C

4. Quick Check:

   Single node deleted = empty list [OK]

Hint: Deleting the only node empties the list [OK]

Common Mistakes:

• Assuming the list still contains the deleted node
• Thinking the list points to itself after deletion
• Expecting an error instead of empty list

2. Which Rust syntax correctly declares a mutable circular linked list node struct with a next pointer?

easy

A. struct Node { data: i32, next: Option }

B. struct Node { data: i32, next: &Node }

C. struct Node { data: i32, next: Node }

D. struct Node { data: i32, next: Option> }

Solution

1. Step 1: Understand Rust ownership for circular references

   Rust disallows direct cyclic ownership. Using Rc allows multiple owners and interior mutability.

2. Step 2: Identify correct syntax for mutable circular linked list node

   struct Node { data: i32, next: Option> } uses Option> which supports cycles and mutability safely.

3. Final Answer:

   struct Node { data: i32, next: Option> } -> Option D

4. Quick Check:

   Use Rc for circular mutable nodes [OK]

Hint: Use Rc and RefCell for mutable circular references in Rust [OK]

Common Mistakes:

• Using plain Box<Node> causes ownership errors
• Using references (&Node) disallows ownership
• Using Node directly causes infinite size error

3. Given this Rust code snippet deleting a node with value 3 from a circular linked list:

let mut head = create_circular_list(vec![1, 2, 3, 4]); delete_node(&mut head, 3); print_list(&head);

What is the printed output?

medium

A. 1 -> 2 -> 4 -> 1 (circular)

B. 1 -> 2 -> 3 -> 4 -> 1 (circular)

C. 2 -> 3 -> 4 -> 2 (circular)

D. 1 -> 2 -> 4 -> null

Solution

1. Step 1: Understand the initial list

   The list is circular with nodes 1, 2, 3, 4 linked in a loop.

2. Step 2: Delete node with value 3

   Node 3 is removed, so the list becomes 1 -> 2 -> 4, then back to 1.

3. Final Answer:

   1 -> 2 -> 4 -> 1 (circular) -> Option A

4. Quick Check:

   Deleted 3, list loops 1-2-4 [OK]

Hint: Deleting node removes it, links neighbors circularly [OK]

Common Mistakes:

• Forgetting to link node 2 to node 4
• Printing null instead of circular loop
• Not deleting the correct node

4. Identify the bug in this Rust function snippet for deleting a node from a circular linked list:

fn delete_node(head: &mut Option>, key: i32) { let mut curr = head.clone().unwrap(); while curr.borrow().data != key { curr = curr.borrow().next.clone().unwrap(); } let next_node = curr.borrow().next.clone(); curr.borrow_mut().next = next_node.unwrap().borrow().next.clone(); }

medium

A. It causes infinite loop if key not found.

B. It does not handle deleting the head node correctly.

C. It leaks memory by not freeing nodes.

D. It uses unwrap() unsafely causing panic.

Solution

1. Step 1: Analyze the while loop condition

   The loop continues until curr's data equals key, but no check if key exists, so it loops infinitely if key missing.

2. Step 2: Check for missing exit condition

   Without a break or stop when full circle is done, infinite loop occurs if key not found.

3. Final Answer:

   It causes infinite loop if key not found. -> Option A

4. Quick Check:

   No key check = infinite loop risk [OK]

Hint: Always check for key existence to avoid infinite loops [OK]

Common Mistakes:

• Assuming key always exists
• Not checking for full circle traversal
• Ignoring unwrap() panic risks

5. How would you delete the head node from a circular linked list in Rust while maintaining the circular structure?

hard

A. Replace head data with next node data and delete next node.

B. Find the last node, set its next to head's next, then update head to head's next.

C. Delete head and leave the last node pointing to old head.

D. Set head to None directly without updating other nodes.

Solution

1. Step 1: Locate the last node in the circular list

   The last node points back to head; find it by traversing until next points to head.

2. Step 2: Update last node's next pointer and head

   Set last node's next to head's next node, then update head to head's next to maintain circularity.

3. Final Answer:

   Find last node, link it to head's next, update head to head's next. -> Option B

4. Quick Check:

   Update last node and head to delete head safely [OK]

Hint: Link last node to new head, then update head [OK]

Common Mistakes:

• Setting head to None breaks circularity
• Not updating last node's next pointer
• Deleting head without adjusting links