Rust Program: Finding Middle element of singly linked list

Rust Linked Lists: Exercise-7 with Solution

Write a Rust program to find the middle element of a singly linked list.

Solution-1 (Odd number of elements):

Rust Code:

// Define the structure for a singly linked list node
struct Node<T> {
    data: T,                // Data stored in the node
    next: Option<Box<Node<T>>>,  // Pointer to the next node
}

impl<T> Node<T> {
    // Function to create a new node
    fn new(data: T) -> Self {
        Node { data, next: None }   // Initialize a new node with given data and no next node
    }
}

// Function to find the middle element of a singly linked list
fn find_middle<'a, T>(head: &'a Option<Box<Node<T>>>) -> Option<&'a T> {
    let mut slow_ptr = head;    // Initialize slow pointer to the head of the list
    let mut fast_ptr = head;    // Initialize fast pointer to the head of the list

    // Iterate through the list until fast pointer reaches the end or the second-to-last node
    while fast_ptr.is_some() && fast_ptr.as_ref().unwrap().next.is_some() {
        slow_ptr = &slow_ptr.as_ref().unwrap().next;   // Move slow pointer one step forward
        fast_ptr = &fast_ptr.as_ref().unwrap().next.as_ref().unwrap().next;   // Move fast pointer two steps forward
    }

    slow_ptr.as_ref().map(|node| &node.data)  // Return a reference to the data of the middle node
}

fn main() {
    // Creating a sample singly linked list: 1 -> 2 -> 3 -> 4 -> 5
    let mut head = Some(Box::new(Node::new(1)));   // Create the head node with data 1
    let mut current = &mut head;   // Initialize a mutable reference to the head node
    for i in 2..=5 {
        let new_node = Box::new(Node::new(i));   // Create a new node with data i
        if let Some(ref mut node) = current {
            node.next = Some(new_node);   // Set the next pointer of the current node to the new node
            current = &mut node.next;   // Move the current pointer to the next node
        }
    }

    // Finding the middle element
    if let Some(mid) = find_middle(&head) {
        println!("The middle element of the list is: {}", mid);   // Print the middle element if found
    } else {
        println!("The list is empty");   // Print a message if the list is empty
    }
} 

Output:

The middle element of the list is: 3

Explanation:

Here is a brief explanation of the above Rust code:

• Node Structure:
• Defines a generic structure Node<T> for a singly linked list node.
• Each node contains two fields:
• data: Holds the actual data of type 'T'.
• next: Points to the next node in the list, wrapped in an "Option" to handle the end of the list.
• Node Implementation:
• Implements methods for the Node<T> structure.
• new: Creates a new node with the provided data and no next node.
• find_middle Function:
• Finds the middle element of a singly linked list.
• Takes a reference to the head of the list (head) as input.
• Initializes two pointers, 'slow_ptr' and 'fast_ptr', both pointing to the head.
• Iterates through the list using the fast pointer, moving it two steps ahead for every step of the slow pointer.
• When the fast pointer reaches the end or the second-to-last node, the slow pointer will be at the middle node.
• Returns an optional reference to the data of the middle node.
• Main Function:
• Creates a sample singly linked list containing nodes with values from 1 to 5.
• Finds the middle element of the list using the 'find_middle' function.
• Prints the middle element if found, or a message indicating that the list is empty otherwise.

Rust Code Editor:

Solution-2 (Even number of elements):

Rust Code:

 // Define the structure for a singly linked list node
struct Node {
    data: T,
    next: Option>>,
}

impl Node {
    // Function to create a new node
    fn new(data: T) -> Self {
        Node { data, next: None }
    }
}

// Function to find the middle elements of a singly linked list
fn find_middle(head: &Option>>) -> Option<(&T, Option<&T>)> {
    let mut slow_ptr = head;
    let mut fast_ptr = head;
    let mut prev_slow_ptr = None;

    while fast_ptr.is_some() && fast_ptr.as_ref().unwrap().next.is_some() {
        prev_slow_ptr = Some(slow_ptr);
        slow_ptr = &slow_ptr.as_ref().unwrap().next;
        fast_ptr = &fast_ptr.as_ref().unwrap().next.as_ref().unwrap().next;
    }

    if let Some(prev) = prev_slow_ptr {
        if let Some(mid2) = slow_ptr.as_ref().map(|node| &node.data) {
            Some((&prev.as_ref().unwrap().data, Some(mid2)))
        } else {
            Some((&prev.as_ref().unwrap().data, None))
        }
    } else {
        None
    }
}

fn main() {
    // Creating a sample singly linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
    let mut head = Some(Box::new(Node::new(1)));
    let mut current = &mut head;
    for i in 2..=6 {
        let new_node = Box::new(Node::new(i));
        if let Some(ref mut node) = current {
            node.next = Some(new_node);
            current = &mut node.next;
        }
    }

    // Finding the middle elements
    if let Some((mid1, mid2)) = find_middle(&head) {
        if let Some(mid2) = mid2 {
            println!("The middle elements of the list are: {} and {}", mid1, mid2);
        } else {
            println!("The middle element of the list is: {}", mid1);
        }
    } else {
        println!("The list is empty");
    }
} 

Output:

The middle elements of the list are: 3 and 4

Explanation:

Here is a brief explanation of the above Rust code:

• Node Structure:
• It defines a generic structure Node<T> for a singly linked list node.
• Each node holds a piece of data of type "T" and an optional reference to the next node (Option<Box<Node<T>>>).
• This structure represents a single node in the linked list.
• Implementation of Node:
• The impl block provides implementations for methods associated with the Node<T> structure.
• It includes a new method that creates a new node with the given data and initializes the 'next' field to 'None'.
• This method simplifies the creation of new nodes.
• find_middle Function:
• It's a function to find the middle elements of a singly linked list.
• It takes a reference to the head of the list (head: &Option<Box<Node<T>>>) and returns an optional tuple containing references to the middle elements.
• The function uses two pointers, 'slow_ptr' and 'fast_ptr', to traverse the list. 'slow_ptr' moves one node at a time, while 'fast_ptr' moves two nodes at a time.
• When 'fast_ptr' reaches the end of the list (None) or its next node is 'None', 'slow_ptr' points to the middle (or middle-left) element.
• main Function:
• It's the entry point of the program.
• Within the main function:
• A sample singly linked list (1 -> 2 -> 3 -> 4 -> 5 -> 6) is created.
• The "find_middle()" function is called to find the middle elements of the list.
• If middle elements are found, they are printed. Otherwise, a message indicating an empty list is printed.

Rust Code Editor:

Previous: Rust Program: Reversing singly linked list.
Next: Rust Set Union Function.