Merging two sorted linked lists, again

I've come across this splendid answer, but it's not the way I would usually write this specific piece of code because I'm not particularly fond of the unbounded loop and breaks.

So I've been trying to rewrite it like I would do in C-like languages (like this), but the task has opened a really messy can of worms and the compiler isn't happy at all. Is there a different way to achieve this result with an iterative approach, or is it one of those cases where it's just a losing battle against the language itself?

2nd link goes to a Python video. Where is your Rust code ?

Sorry, here it is.

Do note that if I de-comment the two breaks inside the while loop, the code works, however I would prefer to have the while loop terminate according to its initial condition. This creates some problems because l1_opt and l2_opt can't be borrowed anymore.

You can just call Option::take to replace the options with None instead of moving them.

Playground, with unit tests added.

Alternatively just set them to None afterwards.

I might like this better, because the reason for doing this requires some thought and seems deserving of a comment:

*next_node_pos = l2_opt;
l2_opt = None;  // we just moved the entire rest of the list so we're at the end

After doing this I looked back at the original function you linked with loop and break and it is so much clearer to me. For instance, in your code, you have this at the end of the loop:

*next_node_pos = &mut next_node_pos.as_mut().unwrap().next;

which unconditionally advances the output pointer by one node. This looks like nonsense to me, because if we took one of the first two branches then we may have inserted more than one node! To really advance to the end, you would need:

while next_node_pos.is_some() {
    *next_node_pos = &mut next_node_pos.as_mut().unwrap().next;
}

Using loop and break as it originally did conveys numerous important facts:

  • The break keyword tells me why those branches do not need to update next_node_pos at all: it's because we're done!!
  • Because the next_node_pos update now only happens in the branch that inserts one node, it is now clear why advancing it a single node suffices.
  • The loop keyword tells me that the only way to exit the loop involves entering one of those branches, so they are not just corner cases; we always finish by attaching a full list.
3 Likes

Now this actually puts everything into a new perspective. I'm so used to always writing this kind of algorithm by advancing one node at a time no matter what, that I failed to recognize why that is suboptimal when one of the lists has already been fully visited.

Thanks to this I can now better appreciate the solution posted by alice in the other thread, as it doesn't seem so unusual anymore.