Traversal and Printing a Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Rust code that prints a singly linked list?

Consider the following Rust code that creates a singly linked list and prints its elements. What will be printed?

DSA Rust

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

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

fn print_list(head: Option<Rc<RefCell<Node>>>) {
    let mut current = head;
    while let Some(node) = current {
        print!("{} -> ", node.borrow().value);
        current = node.borrow().next.clone();
    }
    println!("null");
}

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

    print_list(Some(node1));
}

A null

B 3 -> 2 -> 1 -> null

C 1 -> 2 -> null

D 1 -> 2 -> 3 -> null

💡 Hint

Think about how the list nodes are linked and how the print_list function traverses from head to next nodes.

The list is created with node1 pointing to node2, which points to node3, which points to None. The print_list function starts at node1 and prints values in order: 1, 2, 3, then null.

❓ Predict Output

intermediate

What is the output after traversing this linked list with a loop?

Given this Rust code snippet that traverses a linked list, what will be printed?

DSA Rust

use std::boxed::Box;

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

fn print_list(mut head: Option<Box<Node>>) {
    while let Some(node) = head {
        print!("{} -> ", node.value);
        head = node.next;
    }
    println!("null");
}

fn main() {
    let node3 = Box::new(Node { value: 30, next: None });
    let node2 = Box::new(Node { value: 20, next: Some(node3) });
    let node1 = Box::new(Node { value: 10, next: Some(node2) });

    print_list(Some(node1));
}

A 10 -> 20 -> null

B 30 -> 20 -> 10 -> null

C 10 -> 20 -> 30 -> null

D null

💡 Hint

The list nodes are linked from node1 to node3. The loop prints from head to next until None.

The list starts at node1 with value 10, then node2 with 20, then node3 with 30, then None. The print_list function prints all values in order.

🔧 Debug

advanced

What error does this Rust code produce when traversing a linked list?

This Rust code attempts to traverse and print a linked list. What error will it produce when compiled or run?

DSA Rust

use std::boxed::Box;

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

fn print_list(head: &Option<Box<Node>>) {
    let mut current = head;
    while current.is_some() {
        println!("{}", current.as_ref().unwrap().value);
        current = &current.as_ref().unwrap().next;
    }
}

fn main() {
    let node3 = Box::new(Node { value: 3, next: None });
    let node2 = Box::new(Node { value: 2, next: Some(node3) });
    let node1 = Box::new(Node { value: 1, next: Some(node2) });

    print_list(&Some(node1));
}

A No error, prints: 1 2 3

B error[E0382]: use of moved value: `current`

C error[E0277]: the trait bound `Box<Node>: std::fmt::Display` is not satisfied

D error[E0502]: cannot borrow `*current` as mutable because it is also borrowed as immutable

💡 Hint

Check if the code borrows correctly and if the print statement uses the right syntax.

The code borrows references correctly and prints values by accessing the Option> references. It compiles and prints 1 2 3 each on a new line.

🧠 Conceptual

advanced

How many nodes are printed by this Rust linked list traversal?

Given this Rust code that traverses a linked list, how many nodes will be printed?

DSA Rust

use std::boxed::Box;

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

fn print_list(mut head: Option<Box<Node>>) {
    while let Some(node) = head {
        print!("{} -> ", node.value);
        head = node.next;
    }
    println!("null");
}

fn main() {
    let node3 = Box::new(Node { value: 3, next: None });
    let node2 = Box::new(Node { value: 2, next: Some(node3) });
    let node1 = Box::new(Node { value: 1, next: Some(node2) });

    print_list(Some(node1));
}

A 3

B 1

C 2

D 0

💡 Hint

Count how many nodes are linked starting from node1.

The list has node1 linked to node2, linked to node3, then None. So 3 nodes are printed.

🚀 Application

expert

What is the output after reversing and printing this linked list in Rust?

This Rust code reverses a singly linked list and then prints it. What will be the printed output?

DSA Rust

use std::boxed::Box;

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

fn reverse_list(mut head: Option<Box<Node>>) -> Option<Box<Node>> {
    let mut prev = None;
    while let Some(mut current) = head {
        head = current.next.take();
        current.next = prev;
        prev = Some(current);
    }
    prev
}

fn print_list(mut head: Option<Box<Node>>) {
    while let Some(node) = head {
        print!("{} -> ", node.value);
        head = node.next;
    }
    println!("null");
}

fn main() {
    let node3 = Box::new(Node { value: 3, next: None });
    let node2 = Box::new(Node { value: 2, next: Some(node3) });
    let node1 = Box::new(Node { value: 1, next: Some(node2) });

    let reversed = reverse_list(Some(node1));
    print_list(reversed);
}

A 1 -> 3 -> 2 -> null

B 3 -> 2 -> 1 -> null

C 1 -> 2 -> 3 -> null

D null

💡 Hint

The reverse_list function reverses the links between nodes before printing.

The reverse_list function changes the next pointers so the list order is reversed. The print_list then prints nodes in reversed order: 3, 2, 1.

Practice

1. What does traversing a linked list mean in simple terms?

easy

A. Reversing the order of nodes

B. Adding a new node at the end

C. Visiting each node one by one from start to end

D. Deleting the first node

Solution

1. Step 1: Understand traversal meaning

   Traversal means going through each element in order, like reading a list from start to finish.

2. Step 2: Match with linked list action

   Visiting each node one by one from start to end matches the idea of traversal.

3. Final Answer:

   Visiting each node one by one from start to end -> Option C

4. Quick Check:

   Traversal = Visit nodes in order [OK]

Hint: Traversal means visiting nodes one by one [OK]

Common Mistakes:

• Confusing traversal with adding or deleting nodes
• Thinking traversal means changing node order

2. Which Rust code snippet correctly traverses and prints a singly linked list named list?

easy

A. let mut current = &list.head;
while let Some(node) = current {
println!("{}", node.value);
current = &node.next;
}

B. for node in list {
println!("{}", node.value);
}

C. while list.head.is_some() {
println!("{}", list.head.value);
list.head = list.head.next;
}

D. let mut current = list.head;
loop {
println!("{}", current.value);
}

Solution

1. Step 1: Check traversal logic

   let mut current = &list.head; while let Some(node) = current { println!("{}", node.value); current = &node.next; } uses a mutable reference to current node and loops while current is Some(node), printing value and moving to next node.

2. Step 2: Verify other options

   for node in list { println!("{}", node.value); } tries for loop on list directly (not valid without iterator). while list.head.is_some() { println!("{}", list.head.value); list.head = list.head.next; } mutates list head which is unsafe. let mut current = list.head; loop { println!("{}", current.value); } loops infinitely without checking for None.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Correct traversal uses while let Some(node) = current [OK]

Hint: Use while let Some(node) = current for safe traversal [OK]

Common Mistakes:

• Trying to loop directly over list without iterator
• Not checking for None to stop loop
• Mutating list head during traversal

3. What will be the output of this Rust code that prints a linked list?

struct Node {
    value: i32,
    next: Option,
}

fn print_list(head: &Option) {
    let mut current = head;
    while let Some(node) = current {
        print!("{} -> ", node.value);
        current = &node.next;
    }
    println!("null");
}

fn main() {
    let list = Some(Box::new(Node { value: 1, next: Some(Box::new(Node { value: 2, next: Some(Box::new(Node { value: 3, next: None })) })) }));
    print_list(&list);
}

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 1 2 3 null

D. null

Solution

1. Step 1: Understand list structure

   The list nodes are 1 pointing to 2, which points to 3, which points to None.

2. Step 2: Trace print_list function

   It prints each node's value followed by ' -> ', then prints 'null' at the end.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option B

4. Quick Check:

   Print nodes in order with arrows [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Printing nodes in reverse order
• Missing arrows or null at end
• Printing values without separators

4. Identify the error in this Rust code that tries to print a linked list and fix it:

fn print_list(mut head: Option) {
    while let Some(node) = head {
        println!("{}", node.value);
        head = node.next;
    }
}

medium

A. Code uses wrong print macro println! instead of print!

B. Code does not check for None, causing infinite loop

C. Code does not update head inside the loop

D. Code moves ownership of nodes, so it cannot be reused after printing

Solution

1. Step 1: Analyze ownership in loop

   The code takes ownership of head and nodes inside the loop, consuming the list and preventing reuse.

2. Step 2: Suggest fix using references

   Use references (&Option) and iterate without consuming ownership to allow reuse.

3. Final Answer:

   Code moves ownership of nodes, so it cannot be reused after printing -> Option D

4. Quick Check:

   Ownership moved inside loop causes consumption [OK]

Hint: Use references to avoid moving ownership during traversal [OK]

Common Mistakes:

• Ignoring ownership rules causing compile errors
• Not updating head causing infinite loops
• Confusing print! and println! macros

5. Given a linked list where each node contains an integer, how would you modify the traversal code to print only even values in order?

fn print_even(head: &Option) {
    let mut current = head;
    while let Some(node) = current {
        // Your code here
        current = &node.next;
    }
}

hard

A. Add an if check: if node.value % 2 == 0 { println!("{}", node.value); }

B. Print all values and filter even ones after traversal

C. Change loop to skip nodes with odd values by modifying next pointer

D. Use recursion to print only odd values

Solution

1. Step 1: Add condition inside traversal

   Check if node.value is even using modulo operator and print only if true.

2. Step 2: Keep traversal unchanged

   Continue moving current to next node regardless of value to visit all nodes.

3. Final Answer:

   Add an if check: if node.value % 2 == 0 { println!("{}", node.value); } -> Option A

4. Quick Check:

   Filter values inside traversal with if condition [OK]

Hint: Use if condition inside loop to print only even values [OK]

Common Mistakes:

• Trying to modify next pointer during traversal
• Filtering after traversal instead of during
• Printing odd values instead of even