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