Rust Program: Merge sorted singly linked lists

Rust Linked Lists: Exercise-8 with Solution

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;

// 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
        } else {
            let mut node = l2.take().unwrap();
            l2 = node.next.take();  // Take the ownership of the next 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 };

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

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


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


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.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

Follow us on Facebook and Twitter for latest update.