Get the middle element of LinkedList in a single iteration
Rust Programming Language
Problem
Rust program that gets the middle element of a linked list in a single iteration.
Input
use std::collections::LinkedList;fn main() {let mut list = LinkedList::new();list.push_back(1);list.push_back(2);list.push_back(3);list.push_back(4);list.push_back(5);let mut slow = list.iter();let mut fast = list.iter();while let Some(_) = fast.next() {if let Some(_) = fast.next() {slow.next();}}if let Some(mid) = slow.next() {println!("Middle element: {}", mid);}}{codeBox}
Output
Middle element: 3{codeBox}
Explanation
In this program, we first create a LinkedList of integers. We then create two iterators over the list, slow and fast. The slow iterator advances one element at a time, while the fast iterator advances two elements at a time.
We then use a while loop to iterate over the fast iterator, stopping when it reaches the end of the list (i.e., when fast.next() returns None). At each iteration, we check whether there is another element after the current one in the fast iterator. If there is, we advance the slow iterator one element forward.
After the loop finishes, the slow iterator should be pointing to the middle element of the list (or the first of two middle elements if the list has an even length). We then use an if let statement to print the value of the middle element to the console if it exists.
This is the middle element of the linked list that we created in the program, which has five elements: 1, 2, 3, 4, 5.