Rust Program: Finding Middle element of singly linked list

Last update on December 21 2024 10:21:41 (UTC/GMT +8 hours)

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.