Merge two sorted lists in Rust

Question

I wrote the following code to merge two sorted lists. Is there a way I can improve it?

Possible ideas (not sure how to implement them):

Remove code duplication (setting the returning list node and moving to the next)
Avoid the use of the infinite loop
Avoid the use of panic!

This is the data structure:

type Link = Option<Box<Node>>;

pub struct Node {
    elem: i32,
    next: Link,
}

impl Node {
    fn new(elem: i32) -> Node {
        Node { elem, next: None }
    }
}

And this is the method:

fn merge_sorted_lists(list1: &Link, list2: &Link) -> Link {
    if list1.is_none() || list2.is_none() {
        return None;
    }
    let mut res = None;
    {
        let mut node3 = &mut res;
        let mut node1 = list1;
        let mut node2 = list2;
        loop {
            if let (Some(link1), Some(link2)) = (node1, node2) {
                if link1.elem > link2.elem {
                    *node3 = Some(Box::new(Node::new(link2.elem)));
                    node2 = &link2.next;
                } else {
                    *node3 = Some(Box::new(Node::new(link1.elem)));
                    node1 = &link1.next;
                }
                if let Some(link) = {node3} {
                    node3 = &mut link.next;
                } else {
                    panic!();
                }
            } else if let Some(link1) = node1 {
                *node3 = Some(Box::new(Node::new(link1.elem)));
                node1 = &link1.next;
                if let Some(link) = {node3} {
                    node3 = &mut link.next;
                } else {
                    panic!();
                }
            } else if let Some(link2) = node2 {
                *node3 = Some(Box::new(Node::new(link2.elem)));
                node1 = &link2.next;
                if let Some(link) = {node3} {
                    node3 = &mut link.next;
                } else {
                    panic!();
                }
            } else {
                break;
            }
        }
    }
    res
}

Stargateur · Accepted Answer · 2018-11-11 15:22:42Z

One problem in your current code is that you allocate the merged list, that could be what the user want but that not very flexible, a better way would be to consume the list, and let the user do a copy before if needed.

One other problem is that you have spaghetti code, it's very difficult to maintain and error prone.

you should also use generic to allow an user to have any type in your linked list.

To solve these problem you could use recursion, the typical use case match yours, so I would simply rework all your code to use it:

type Link<T> = Option<Box<Node<T>>>;

#[derive(Debug, Clone)]
pub struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> Node<T> {
    // rework of new to make it more flexible
    fn new(elem: T, next: Link<T>) -> Self {
        Self { elem, next }
    }

    // next allow to change to linked node and to return the old one
    fn next(&mut self, next: Link<T>) -> Link<T> {
        std::mem::replace(&mut self.next, next)
    }

    fn elem(&self) -> &T {
        &self.elem
    }

    // now we take by value and allow user to have a flexible control with f
    fn merge_by<F>(a: Link<T>, b: Link<T>, accu: Link<T>, f: F) -> Link<T>
    where
        F: Fn(&T, &T) -> bool, 
    {
        match (a, b) {
            (Some(mut a), Some(mut b)) => {
                if f(a.elem(), b.elem()) {
                    Self::merge_by(a.next(accu), Some(b), Some(a), f)
                } else {
                    Self::merge_by(Some(a), b.next(accu), Some(b), f)
                }
            }
            (Some(a), None) => Self::rev(accu, Some(a)),
            (None, Some(b)) => Self::rev(accu, Some(b)),
            (None, None) => Self::rev(accu, None),
        }
    }

    // rev is needed when you deal with list
    fn rev(list: Link<T>, accu: Link<T>) -> Link<T> {
        match list {
            Some(mut list) => Self::rev(list.next(accu), Some(list)),
            None => accu,
        }
    }

}

fn main() {
    let a = Some(Box::new(Node::new(21, Some(Box::new(Node::new(42, None))))));
    println!("{:#?}", a);

    let b = Some(Box::new(Node::new(1, Some(Box::new(Node::new(2, None))))));
    println!("{:#?}", b);

    let c = Node::merge_by(a, b, None, std::cmp::PartialEq::eq);
    println!("{:#?}", c);
}

Stack Exchange Network

Merge two sorted lists in Rust

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Merge two sorted lists in Rust

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions