Rust to assembly: Recursive linked list merge
Introduction
https://www.howtocodeit.com/articles/rust-ownership-explained-linked-lists
Recurisive linked list merge
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
pub fn merge(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match (list1, list2) {
(None, None) => None,
(Some(node), None) | (None, Some(node)) => Some(node),
(Some(mut node1), Some(mut node2)) => {
if node1.val < node2.val {
node1.next = merge(node1.next, Some(node2));
Some(node1)
} else {
node2.next = merge(Some(node1), node2.next);
Some(node2)
}
}
}
}
Compiler Explorer: recursive linked list merge
https://godbolt.org/z/8osa4vEE4
Convert recursive linked list merge to iterative
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
pub fn merge(mut list1: Option<Box<ListNode>>, mut list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy_head = ListNode { val: 0, next: None };
let mut tail = &mut dummy_head;
while let (Some(mut node1), Some(mut node2)) = (list1.take(), list2.take()) {
if node1.val < node2.val {
list1 = node1.next.take();
tail.next = Some(node1);
} else {
list2 = node2.next.take();
tail.next = Some(node2);
}
tail = tail.next.as_mut().unwrap();
}
if list1.is_some() {
tail.next = list1;
} else if list2.is_some() {
tail.next = list2;
}
dummy_head.next
}
Compiler Explorer: iterative linked list merge
https://godbolt.org/z/T3oh943v9
Tail call recursive linked list merge
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
pub fn merge(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
fn merge_tail(
list1: Option<Box<ListNode>>,
list2: Option<Box<ListNode>>,
acc: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
match (list1, list2) {
(None, None) => acc,
(Some(node), None) | (None, Some(node)) => {
append(acc, Some(node)) // append remaining node to accumulator
}
(Some(mut node1), Some(mut node2)) => {
if node1.val < node2.val {
let next1 = node1.next.take();
let new_acc = append(acc, Some(node1));
merge_tail(next1, Some(node2), new_acc)
} else {
let next2 = node2.next.take();
let new_acc = append(acc, Some(node2));
merge_tail(Some(node1), next2, new_acc)
}
}
}
}
fn append(
mut acc: Option<Box<ListNode>>,
node: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
if acc.is_none() {
return node;
}
let mut current = acc.as_mut().unwrap();
while let Some(ref mut next) = current.next {
current = next;
}
current.next = node;
acc
}
merge_tail(list1, list2, None)
}
Compiler Explorer: tail call recursive linked list merge
https://godbolt.org/z/77hao5s48
