Rust Program to Detect loop in a LinkedList

Detect loop in a LinkedList

Rust Programming Language

Detect loop in a LinkedList


Rust program that detects if a linked list has a loop using the Floyd's cycle-finding algorithm.


use std::collections::HashSet;

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>) { = Some(Box::new(next));

fn has_loop<T>(head: &Node<T>) -> bool {
    let mut slow = head;
    let mut fast = head;

    while && {
        slow = &*;
        fast = &*;

        if slow as *const Node<T> == fast as *const Node<T> {
            return true;


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);

    n5.add_next(n2); // creating a loop

    println!("Has loop: {}", has_loop(&n1)); // should print true


Has loop: true{codeBox}


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.

Post a Comment