How can I use Rust to CLONE a linked list?

I'm a rookie in Rust, and currently I'm actively using Rust to code LeetCode practice.

Now I'm working on this one, Copy List with Random Pointer, where nobody has even provided a Rust version answer.

I tried for a while but then I realised it's insanely hard for me to copy even a simple linked list in Rust.

Thanks for the help from @cafce25 that we can directly use .clone() to implement it, which is amazing. However, I'm wondering if there is any implementation that we don't need to use such a mighty weapon .clone() so that I could delve from this point.

Could anyone give me a favour? Thank you pretty much.

Some interfaces are provided as below and please feel free to modify function signatures.

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    pub fn new(val: i32) -> Self {
        ListNode {
            val,
            next: None,
        }
    }

    pub fn copyList(head: &Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        todo!();
    }
}

> However, I'm wondering if there is any implementation that we don't need to use such a mighty weapon .clone() so that I could delve from this point.

First of all, it seems reasonable for copyList to actually take a reference to a list node itself, and the more idiomatic name is copy_list:

    pub fn copy_list(head: &ListNode) -> ListNode {
        todo!()
    }

(no ; at the end because we want to return a result, and the semicolon would make the function return ()). The first step is (not necessarily, but it's useful) to pattern-match the argument, and we also know we want to return a ListNode at the end, so let's construct it there:

    pub fn copy_list(head: &ListNode) -> ListNode {
        let ListNode { val, next } = head;
        let copied_next = todo!();
        ListNode { val: todo!(), next: copied_next }
    }

What remains is to calculate copied_next (ok, and val, but it's much simpler). I won't give you the full code for it, but some hints:

1. Consider the types of next and copied_next;
2. You can use either pattern matching on next or Option::map and Box::map;
3. You'll call copy_list recursively somewhere inside that pattern match or map's argument.

(And simply next.clone() would work too, and is approximately what the generated clone() function does, which is why it clones the entire list.)

Thanks for the inspiration from @Alexey Romanov. After several hours of debugging, I implemented a plain way to clone a linked list as below:

#[derive(PartialEq, Eq, Debug, Clone)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    pub fn new(val: i32) -> Self {
        ListNode {
            val,
            next: None,
        }
    }

    pub fn clone_linked_list(mut head: &Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(-1));
        let mut pre = &mut dummy; 
        while let Some(node) = head {
            let new_node = Box::new(ListNode::new(node.val));
            pre.next.replace(new_node);
            pre = pre.next.as_mut().unwrap();
            head = &node.next;
        }
        dummy.next
    }
}

Please feel free to give any suggestions. Thank you a lot.