﻿ Rust Program: Find Middle element of singly linked list

# 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 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 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:

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿