Rust Program: Reversing singly linked list

Last update on December 21 2024 10:19:19 (UTC/GMT +8 hours)

Write a Rust program to reverse a singly linked list.

Sample Solution:

Rust Code:

// Define the Node struct to represent individual nodes in the linked list
#[derive(Debug)]
struct Node<T> {
    data: T,                     // Data stored in the node
    next: Option<Box<Node<T>>>, // Pointer to the next node
}

// Define the SinglyLinkedList struct to represent the linked list
struct SinglyLinkedList<T> {
    head: Option<Box<Node<T>>>, // Pointer to the head of the linked list
}

impl<T> SinglyLinkedList<T> {
    // Method to reverse the linked list
    fn reverse(&mut self) {
        let mut prev = None; // Initialize a placeholder for the previous node
        let mut current = self.head.take(); // Take ownership of the current head node

        // Traverse the linked list
        while let Some(mut node) = current {
            // Move the next pointer to the previous node
            let next = node.next.take();
            // Set the next pointer of the current node to the previous node
            node.next = prev.take();
            // Update the previous node to the current node
            prev = Some(node);
            // Move to the next node in the original list
            current = next;
        }

        // Set the head of the linked list to the last node (previously the first node)
        self.head = prev;
    }
}

fn main() {
    // Create a new linked list
    let mut list = SinglyLinkedList {
        head: Some(Box::new(Node { data: 1, next: None })),
    };

    // Insert some nodes into the linked list
    list.head = Some(Box::new(Node { data: 2, next: list.head.take() }));
    list.head = Some(Box::new(Node { data: 3, next: list.head.take() }));
    list.head = Some(Box::new(Node { data: 4, next: list.head.take() }));
    list.head = Some(Box::new(Node { data: 5, next: list.head.take() }));

    // Print the original linked list
    println!("Original Linked List: {:?}", list.head);

    // Reverse the linked list
    list.reverse();

    // Print the reversed linked list
    println!("Reversed Linked List: {:?}", list.head);
}

Output:

Original Linked List: Some(Node { data: 5, next: Some(Node { data: 4, next: Some(Node { data: 3, next: Some(Node { data: 2, next: Some(Node { data: 1, next: None }) }) }) }) })
Reversed Linked List: Some(Node { data: 1, next: Some(Node { data: 2, next: Some(Node { data: 3, next: Some(Node { data: 4, next: Some(Node { data: 5, next: None }) }) }) }) })

Explanation:

Here is a brief explanation of the above Rust code:

• Node struct: Represents individual nodes in the linked list. Each node contains data ('data') and a pointer to the next node ('next'), which is an 'Option' wrapping a 'Box' pointing to another 'Node'.
• SinglyLinkedList struct: Represents the linked list itself. It contains a pointer to the head of the linked list ('head'), which is an 'Option' wrapping a 'Box' pointing to the first 'Node'.
• impl block for SinglyLinkedList: Implements methods for the linked list. In this case, it defines a method "reverse()" to reverse the linked list.
• reverse method: Reverses the linked list by iteratively updating the pointers of each node to point to the previous node.
• main function: Entry point of the program. It shows the usage of the linked list by creating a list, inserting nodes, reversing the list, and printing both the original and reversed lists.

Rust Code Editor:

Previous: Rust Program: Deleting Node by position from singly linked list.
Next: Rust Program: Finding Middle element of singly linked list.