Rust Program to Detect loop in a LinkedList

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 loop

println!("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.