Rust Program to Detect loop in a LinkedList


Detect loop in a LinkedList

Rust Programming Language


Detect loop in a LinkedList


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.


Post a Comment