Rust Program: Merge sorted singly linked lists

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

Write a Rust program to merge two sorted singly linked lists into one sorted linked list.

Sample Solution:

Rust Code:

// Define the structure for a singly linked list node
struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

impl Node {
    // Function to create a new node
    fn new(data: i32) -> Self {
        Node { data, next: None }
    }
}


// Function to print the elements of a linked list
fn print_list(head: &Option<Box<Node>>) {
    print!("Linked List: ");
    let mut current = head;
    while let Some(node) = current {
        print!("{} -> ", node.data);
        current = &node.next;
    }
    println!("None");
}

// Function to merge two sorted linked lists into one sorted linked list
fn merge_sorted_lists(mut l1: Option<Box<Node>>, mut l2: Option<Box<Node>>) -> Option<Box<Node>> {
    let mut result = None;
    let mut tail = &mut result;

    // Merge the lists until one of them becomes empty
    while let (Some(node1), Some(node2)) = (l1.as_mut(), l2.as_mut()) {
        let next_node = if node1.data < node2.data {
            let mut node = l1.take().unwrap();
            l1 = node.next.take();  // Take the ownership of the next node
            node
        } else {
            let mut node = l2.take().unwrap();
            l2 = node.next.take();  // Take the ownership of the next node
            node
        };
        
        *tail = Some(next_node);
        tail = &mut tail.as_mut().unwrap().next;
    }

    // Add the remaining nodes from the non-empty list
    *tail = if l1.is_some() { l1 } else { l2 };

    result
}
 
fn main() {
    // Create two sorted linked lists
    let mut l1 = Some(Box::new(Node::new(1)));
    l1.as_mut().unwrap().next = Some(Box::new(Node::new(3)));
    l1.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new(5)));

    let mut l2 = Some(Box::new(Node::new(2)));
    l2.as_mut().unwrap().next = Some(Box::new(Node::new(4)));
    l2.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(Node::new(6)));

    // Print the original lists
    print_list(&l1);
    print_list(&l2);

    // Merge the lists and print the merged list
    let merged_list = merge_sorted_lists(l1, l2);
    print_list(&merged_list);
} 

Output:

Linked List: 1 -> 3 -> 5 -> None
Linked List: 2 -> 4 -> 6 -> None
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

Explanation:

Here is a brief explanation of the above Rust code:

• Node structure:
• Defines a structure "Node" representing a node in a singly linked list.
• Each node contains an 'i32' value 'data' and an Option<Box<Node>> 'next', representing a pointer to the next node in the list.
• Node implementation:
• Implement associated functions for the "Node" structure.
• Provides a function "new()" to create a new node with the given data.
• Print List Function:
• Define a function "print_list()" to print the elements of a linked list.
• It takes a reference to the head of the list (&Option<Box<Node>>) as input.
• Iterates through the list, printing each node's data sequentially.
• Merge Sorted Lists Function:
• Defines a function "merge_sorted_lists()" to merge two sorted linked lists into one sorted linked list.
• It takes ownership of two sorted linked lists (l1 and l2) as input and returns a new sorted linked list.
• Merge the lists by comparing the data of the nodes and rearranging the pointers accordingly.
• Maintain a 'result' variable to store the merged list and a 'tail' pointer to keep track of the end of the merged list.
• Main function:
• Create two sorted linked lists (l1 and l2) with some predefined values.
• Prints the original lists using the "print_list()" function.
• Merges the lists using the "merge_sorted_lists()" function and print the merged list.

Rust Code Editor:

Previous: Rust Program: Finding Middle element of singly linked list.
Next: Rust Program: Remove duplicates from singly linked list.