Rust Program: Finding Middle element of singly linked list
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.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.