﻿ Rust Program: Merge sorted singly linked lists

# 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
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:

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿