Detect loop in a LinkedList
Rust Programming Language
Problem
Rust program that detects if a linked list has a loop using the Floyd's cycle-finding algorithm.
Input
use std::collections::HashSet;#[derive(Debug)]struct Node<T> {data: T,next: Option<Box<Node<T>>>,}impl<T> Node<T> {fn new(data: T) -> Self {Node { data, next: None }}fn add_next(&mut self, next: Node<T>) {self.next = Some(Box::new(next));}}fn has_loop<T>(head: &Node<T>) -> bool {let mut slow = head;let mut fast = head;while fast.next.is_some() && fast.next.as_ref().unwrap().next.is_some() {slow = &*slow.next.as_ref().unwrap();fast = &*fast.next.as_ref().unwrap().next.as_ref().unwrap();if slow as *const Node<T> == fast as *const Node<T> {return true;}}false}fn main() {let mut n1 = Node::new(1);let mut n2 = Node::new(2);let mut n3 = Node::new(3);let mut n4 = Node::new(4);let mut n5 = Node::new(5);n1.add_next(n2);n2.add_next(n3);n3.add_next(n4);n4.add_next(n5);n5.add_next(n2); // creating a loopprintln!("Has loop: {}", has_loop(&n1)); // should print true}{codeBox}
Output
Has loop: true{codeBox}
Explanation
This program defines a Node struct that represents a node in a linked list. Each node contains a piece of data and a pointer to the next node in the list. The add_next method is used to set the next field of a node to another node.
The has_loop function takes a reference to the head of a linked list and returns a boolean indicating whether the list contains a loop. It uses the Floyd's cycle-finding algorithm to detect the loop by using two pointers, one moving one step at a time and the other moving two steps at a time. If the two pointers ever meet, there is a loop in the list.
The main function creates a linked list with five nodes and creates a loop by setting the next field of the last node to the second node. It then calls the has_loop function to check if the list contains a loop and prints the result.