Swapping two elements of a singly-linked list
Run Rustfmt. It well automatically tell you such things as:


Idiomatic Rust uses 4-space indents.
Match arms without curly braces have trailing commas
You don't need to prefix paths in use with ::; that's the default.

You don't need #![allow(dead_code)] and it's better to not disable warnings that broadly.
It's usual to import only the module, not the free function, and then namespace the function. For example, mem::replace.
mem::replace(&amp;mut /* ... */, None) is equivalent to Option::take
You can also replace some usages of mem::swap with Option::take and direct assignment. This means you don't need to use functions from mem at all.


#[derive(Debug)]
pub struct List&lt;T&gt; {
    list: Node&lt;T&gt;,
}

type Node&lt;T&gt; = Option&lt;Box&lt;Link&lt;T&gt;&gt;&gt;;

#[derive(Debug)]
struct Link&lt;T&gt; {
    head: T,
    tail: Node&lt;T&gt;,
}

impl&lt;T&gt; List&lt;T&gt; {
    pub fn push(&amp;mut self, elem: T) {
        self.list = Some(Box::new(Link {
            head: elem,
            tail: self.list.take(),
        }));
    }

    pub fn pop(&amp;mut self) -&gt; Option&lt;T&gt; {
        match self.list.take() {
            Some(next_box) =&gt; {
                let next = *next_box;
                self.list = next.tail;
                Some(next.head)
            }
            _ =&gt; None,
        }
    }

    // First attempt: Use push+pop. Not perfect, as we move the values
    // in and out, and if they're larger, we waste resources.
    pub fn bubble(&amp;mut self) -&gt; bool {
        if let Some(first) = self.pop() {
            if let Some(second) = self.pop() {
                self.push(first);
                self.push(second);
                return true;
            } else {
                self.push(first);
            }
        }
        false
    }

    // Learning from the above attempt, I created another push+pop
    // functions that don't move values, just Boxes instead.

    // Any tail of 'singleton' is silently discarded.
    fn push_singleton(&amp;mut self, mut singleton: Box&lt;Link&lt;T&gt;&gt;) {
        singleton.tail = self.list.take();
        self.list = Some(singleton);
    }

    fn pop_singleton(&amp;mut self) -&gt; Node&lt;T&gt; {
        match self.list.take() {
            Some(mut next_box) =&gt; {
                self.list = next_box.tail.take();
                Some(next_box)
            }
            _ =&gt; None,
        }
    }

    // Otherwise the implementation is very similar to 'bubble' above.
    pub fn bubble2(&amp;mut self) -&gt; bool {
        if let Some(first_box) = self.pop_singleton() {
            if let Some(second_box) = self.pop_singleton() {
                self.push_singleton(first_box);
                self.push_singleton(second_box);
                return true;
            } else {
                self.push_singleton(first_box);
            }
        }
        false
    }

    // Third attempt: Directly unpack the first two nodes and combine them
    // back together.
    pub fn bubble3(&amp;mut self) -&gt; bool {
        if let Some(mut first_box) = self.list.take() {
            if let Some(mut second_box) = first_box.tail.take() {
                first_box.tail = second_box.tail.take();
                second_box.tail = Some(first_box);
                *self = List {
                    list: Some(second_box),
                };
                return true;
            } else {
                *self = List {
                    list: Some(first_box),
                };
            }
        }
        false
    }
}

fn main() {}


For what it's worth, I prefer bubble2 as the implementation is better factored and has helper functions.

I'm not a big fan of the word "singleton" here, as that feels like a misuse of the term. I don't have a great alternative name other than {push,pop}_boxed though.