Traversal of Circular Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of traversing a circular linked list once

What is the printed output of the following Rust code that traverses a circular linked list exactly once?

DSA Rust

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

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

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

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

    let mut current = node1.clone();
    print!("Traversal: ");
    loop {
        print!("{} -> ", current.borrow().data);
        current = current.borrow().next.as_ref().unwrap().clone();
        if Rc::ptr_eq(&current, &node1) {
            break;
        }
    }
    print!("null");
}

A Traversal: 1 -> null

B Traversal: 1 -> 2 -> 3 -> null

C Traversal: 1 -> 2 -> 3 -> 1 -> null

D Traversal: 1 -> 2 -> null

💡 Hint

Think about stopping the traversal when you reach the starting node again.

The code prints each node's data starting from node1 and stops when it reaches node1 again, so it prints 1, 2, 3 and then stops, printing 'null' at the end.

❓ Predict Output

intermediate

Output when traversing circular linked list with 4 nodes

What is the output of this Rust code that traverses a circular linked list with 4 nodes once?

DSA Rust

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

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

fn main() {
    let node1 = Rc::new(RefCell::new(Node { data: 10, next: None }));
    let node2 = Rc::new(RefCell::new(Node { data: 20, next: None }));
    let node3 = Rc::new(RefCell::new(Node { data: 30, next: None }));
    let node4 = Rc::new(RefCell::new(Node { data: 40, next: None }));

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());
    node3.borrow_mut().next = Some(node4.clone());
    node4.borrow_mut().next = Some(node1.clone()); // circular link

    let mut current = node1.clone();
    print!("Traversal: ");
    loop {
        print!("{} -> ", current.borrow().data);
        current = current.borrow().next.as_ref().unwrap().clone();
        if Rc::ptr_eq(&current, &node1) {
            break;
        }
    }
    print!("null");
}

A Traversal: 10 -> 20 -> 30 -> null

B Traversal: 10 -> 20 -> 30 -> 40 -> 10 -> null

C Traversal: 10 -> 20 -> 30 -> 40 -> null

D Traversal: 10 -> null

💡 Hint

Remember to stop when you reach the start node again.

The loop prints all 4 nodes once and stops when it reaches the first node again, so it prints 10, 20, 30, 40 and then 'null'.

🔧 Debug

advanced

Identify the error in circular linked list traversal code

What error will this Rust code produce when trying to traverse a circular linked list?

DSA Rust

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

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

fn main() {
    let node1 = Rc::new(RefCell::new(Node { data: 5, next: None }));
    let node2 = Rc::new(RefCell::new(Node { data: 6, next: None }));

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node1.clone()); // circular link

    let mut current = node1.clone();
    print!("Traversal: ");
    while current.borrow().next.is_some() {
        print!("{} -> ", current.borrow().data);
        current = current.borrow().next.as_ref().unwrap().clone();
    }
    print!("null");
}

A Infinite loop causing the program to hang

B SyntaxError due to missing semicolon

C Panic at unwrap on None value

D Prints only one node and stops

💡 Hint

Check the loop condition and how it handles circular links.

The loop condition checks if next is Some, which is always true in a circular list, so it never stops, causing an infinite loop.

🧠 Conceptual

advanced

Why use Rc and RefCell in Rust circular linked list?

Why do we use Rc> for nodes in a circular linked list in Rust?

A To allow multiple ownership and interior mutability of nodes

B To prevent any mutation of nodes after creation

C To make nodes immutable and thread-safe automatically

D To avoid using pointers and references altogether

💡 Hint

Think about how circular references and mutability work in Rust.

Rc allows multiple owners of the same node (needed for circular links), and RefCell allows mutating the node even when it is inside an Rc.

❓ Predict Output

expert

Output after modifying data during circular linked list traversal

What is the output of this Rust code that modifies node data during traversal of a circular linked list?

DSA Rust

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

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

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

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

    let mut current = node1.clone();
    print!("Traversal after increment: ");
    loop {
        let mut node_ref = current.borrow_mut();
        node_ref.data += 10;
        print!("{} -> ", node_ref.data);
        drop(node_ref);
        current = current.borrow().next.as_ref().unwrap().clone();
        if Rc::ptr_eq(&current, &node1) {
            break;
        }
    }
    print!("null");
}

A Traversal after increment: 11 -> 22 -> 33 -> null

B Traversal after increment: 1 -> 2 -> 3 -> null

C Traversal after increment: 10 -> 20 -> 30 -> null

D Traversal after increment: 11 -> 12 -> 13 -> null

💡 Hint

Each node's data is increased by 10 exactly once during traversal.

The code adds 10 to each node's data during traversal, so original 1,2,3 become 11,12,13 respectively.

Practice

1. What is the main difference between a circular linked list and a regular singly linked list?

easy

A. In a circular linked list, nodes have two pointers instead of one.

B. In a circular linked list, the last node points back to the first node.

C. In a circular linked list, nodes are stored in an array.

D. In a circular linked list, nodes cannot be traversed.

Solution

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

   A circular linked list connects the last node back to the first node, forming a circle.

2. Step 2: Compare with a regular singly linked list

   A regular singly linked list ends with a null pointer, not looping back.

3. Final Answer:

   In a circular linked list, the last node points back to the first node. -> Option B

4. Quick Check:

   Last node points to first node = A [OK]

Hint: Remember: circular means last node links back to start [OK]

Common Mistakes:

• Thinking circular lists have two pointers per node
• Confusing circular linked list with doubly linked list
• Assuming nodes are stored in arrays

2. Which Rust code snippet correctly starts traversal of a circular linked list from the head node?

easy

A. let mut current = head;
loop {
println!("{}", current.data);
current = current.next.unwrap();
if current == head { break; }
}

B. let mut current = head;
while current != None {
println!("{}", current.data);
current = current.next;
}

C. for node in head {
println!("{}", node.data);
}

D. let mut current = head;
loop {
println!("{}", current.data);
current = current.next.unwrap();
}

Solution

1. Step 1: Identify correct loop structure for circular traversal

   let mut current = head; loop { println!("{}", current.data); current = current.next.unwrap(); if current == head { break; } } uses a loop that breaks when current returns to head, correctly handling circular traversal.

2. Step 2: Check other options for errors

   let mut current = head; while current != None { println!("{}", current.data); current = current.next; } uses while with None check, which is incorrect for circular lists. for node in head { println!("{}", node.data); } uses for loop on head, invalid syntax. let mut current = head; loop { println!("{}", current.data); current = current.next.unwrap(); } loops infinitely without break.

3. Final Answer:

   let mut current = head; loop { println!("{}", current.data); current = current.next.unwrap(); if current == head { break; } } -> Option A

4. Quick Check:

   Loop until current == head = A [OK]

Hint: Use loop with break when current equals head [OK]

Common Mistakes:

• Using while with None check in circular list
• Forgetting to break loop on returning to head
• Using invalid for loop syntax on linked list

3. What will be the output of the following Rust code that traverses a circular linked list with nodes containing values 10, 20, 30?

let mut current = head;
loop {
    print!("{} ", current.data);
    current = current.next.unwrap();
    if current == head { break; }
}

medium

A. Runtime error due to infinite loop

B. 10 20 30 10

C. 20 30 10

D. 10 20 30

Solution

1. Step 1: Understand traversal logic

   The loop prints current.data, moves to next, and breaks when current equals head again.

2. Step 2: Trace the output

   Starting at 10, prints 10, moves to 20, prints 20, moves to 30, prints 30, moves to 10 (head), breaks loop.

3. Final Answer:

   10 20 30 -> Option D

4. Quick Check:

   Print nodes once until back to head = D [OK]

Hint: Stop printing when current node equals head again [OK]

Common Mistakes:

• Printing extra head node again after loop
• Assuming infinite loop without break
• Starting traversal from wrong node

4. Identify the bug in this Rust code snippet for traversing a circular linked list:

let mut current = head;
while current != head {
    println!("{}", current.data);
    current = current.next.unwrap();
}

medium

A. The code causes infinite loop because no break condition.

B. The unwrap() causes panic if next is None.

C. The loop never executes because current == head initially.

D. The println! macro is used incorrectly.

Solution

1. Step 1: Analyze loop condition

   The while loop condition is current != head, but current starts as head, so condition is false immediately.

2. Step 2: Understand effect on execution

   Loop body never runs, so no traversal happens.

3. Final Answer:

   The loop never executes because current == head initially. -> Option C

4. Quick Check:

   Loop condition false at start = B [OK]

Hint: Check initial loop condition matches traversal logic [OK]

Common Mistakes:

• Using while current != head instead of loop with break
• Ignoring that current starts at head
• Assuming unwrap() always safe without checking

5. You want to sum all values in a circular linked list of integers using Rust. Which approach correctly avoids infinite loops and sums all nodes exactly once?

hard

A. Use a loop starting at head, add current.data, move to next, break when current == head again.

B. Use a while loop checking current != None, add current.data, move to next.

C. Use recursion without base case to traverse nodes and sum values.

D. Use a for loop over head assuming it implements Iterator.

Solution

1. Step 1: Understand circular list traversal for summation

   We must visit each node once and stop when we return to head to avoid infinite loops.

2. Step 2: Evaluate options

   Use a loop starting at head, add current.data, move to next, break when current == head again. uses loop with break on current == head, correctly summing once. Use a while loop checking current != None, add current.data, move to next. uses None check which is invalid for circular lists. Use recursion without base case to traverse nodes and sum values. causes infinite recursion. Use a for loop over head assuming it implements Iterator. assumes Iterator trait which is not standard for linked lists.

3. Final Answer:

   Use a loop starting at head, add current.data, move to next, break when current == head again. -> Option A

4. Quick Check:

   Loop with break on head = C [OK]

Hint: Break loop when current node equals head to avoid repeats [OK]

Common Mistakes:

• Using None checks in circular lists
• Recursing without base case causing stack overflow
• Assuming linked list implements Iterator trait