# Zipping together two linked lists

Hey I was working on a leetcode challenge to get to know rust better and I found this problem where you merge together two sorted linked lists. I figured this would be pretty simple since I've done similar things in Java before, but I'm constantly fighting the borrow checker for this one. So here is the code that I've written:

``````// Definition for singly-linked list.
#[derive(PartialEq, Eq, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}

impl ListNode {
#[inline]
fn new(val: i32) -> Self {
ListNode {
next: None,
val
}
}
}

struct Solution;

impl Solution {
pub fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut l1_t = &l1;
let mut l2_t = &l2;

let mut list : Option<Box<ListNode>> = None;

{
let list_ptr : &mut Option<Box<ListNode>> = &mut list;

'merge: loop {
match (l1_t, l2_t) {
(None, None) => break 'merge,
(Some(ele1), None) => {
let mut tmp = Box::new(ListNode::new(ele1.val));
list_ptr.as_mut().unwrap().next = Some(tmp);

l1_t = &l1_t.as_ref().unwrap().next;
// list_ptr = &mut list_ptr.as_mut().unwrap().next;
},
(None, Some(ele2)) => {
let mut tmp = Box::new(ListNode::new(ele2.val));
list_ptr.as_mut().unwrap().next = Some(tmp);

l2_t = &l2_t.as_ref().unwrap().next;
},
(Some(ele1), Some(ele2)) => {
let mut tmp1 = Box::new(ListNode::new(ele1.val));
let mut tmp2 = Box::new(ListNode::new(ele2.val));

tmp1.next = Some(tmp2);
list_ptr.as_mut().unwrap().next = Some(tmp1);

l1_t = &l1_t.as_ref().unwrap().next;
l2_t = &l2_t.as_ref().unwrap().next;
}
}
}
}
list
}
}

fn main() {
println!("Okay");
}
``````

The definition for the `ListNode` was given by the question so that's not really mine. My strategy for this was basically to have a tail pointer and just use that to append two new entries from `l1` and `l2` to my new `list`. I basically have tail pointers working for the `l1_t` and `l2_t` pointers, but those are immutable whereas I need the list tail pointer to be mutable. When I un-comment the line `list_ptr = &mut list_ptr.as_mut().unwrap().next;` I obviously get the full wrath of the borrow checker with:

``````error[E0499]: cannot borrow `*list_ptr` as mutable more than once at a time
|
36 |                         list_ptr.as_mut().unwrap().next = Some(tmp);
|                         ^^^^^^^^ second mutable borrow occurs here
...
39 |                         list_ptr = &mut list_ptr.as_mut().unwrap().next;
|                                         -------- first mutable borrow occurs here
...
59 |         }
|         - first borrow ends here

error[E0506]: cannot assign to `list_ptr` because it is borrowed
|
39 |                         list_ptr = &mut list_ptr.as_mut().unwrap().next;
|                         ^^^^^^^^^^^^^^^^--------^^^^^^^^^^^^^^^^^^^^^^^
|                         |               |
|                         |               borrow of `list_ptr` occurs here
|                         assignment to borrowed `list_ptr` occurs here

error[E0384]: cannot assign twice to immutable variable `list_ptr`
|
29 |             let list_ptr : &mut Option<Box<ListNode>> = &mut list;
|                 -------- first assignment to `list_ptr`
...
39 |                         list_ptr = &mut list_ptr.as_mut().unwrap().next;
|                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot assign twice to immutable variable

error[E0499]: cannot borrow `*list_ptr` as mutable more than once at a time
|
39 |                         list_ptr = &mut list_ptr.as_mut().unwrap().next;
|                                         ^^^^^^^^ mutable borrow starts here in previous iteration of loop
...
59 |         }
|         - mutable borrow ends here

error[E0499]: cannot borrow `*list_ptr` as mutable more than once at a time
|
39 |                         list_ptr = &mut list_ptr.as_mut().unwrap().next;
|                                         -------- first mutable borrow occurs here
...
43 |                         list_ptr.as_mut().unwrap().next = Some(tmp);
|                         ^^^^^^^^ second mutable borrow occurs here
...
59 |         }
|         - first borrow ends here

error[E0499]: cannot borrow `*list_ptr` as mutable more than once at a time
|
39 |                         list_ptr = &mut list_ptr.as_mut().unwrap().next;
|                                         -------- first mutable borrow occurs here
...
52 |                         list_ptr.as_mut().unwrap().next = Some(tmp1);
|                         ^^^^^^^^ second mutable borrow occurs here
...
59 |         }
|         - first borrow ends here

error: aborting due to 6 previous errors

Some errors occurred: E0384, E0499, E0506.
``````

What are some changes I could make to actually get this to work? What exactly am I missing here that would actually let me get to testable code?

`TL;DR` Code broke, borrow checker mad, pls help References are not pointers, in the same sense that pointers are not integers. Even if technically they're implemented similarly, their meaning and usage is intended to be quite different.

References in Rust are compile-time locks.

When you take a reference of `l1`, you lock all of `l1` to be read-only. And after that it's game over, because you can't change any element of that list.

2 Likes

So what do you suggest I do instead?

In general, the borrow checker doesn't understand linked lists: Learning Rust With Entirely Too Many Linked Lists so I'm not sure if that is even possible without help of raw pointers.

I haven't analyzed the problem deeply, but you might try using only owned values (no `&` anywhere!), and `Option.take()` to unlink elements if you need to.

Or use `*mut Box<ListNode>` the same way you would in C.

1 Like

Thank you!

That's pretty much the story of life with Linked Lists As an idea for a similar-but-different challenge in rust, consider making an iterator that lazily merges two sorted iterators.

2 Likes

I think it's possible to do this the way you want to and without unsafe. I suggest you try to implement a `copy(&Option<Box<ListNode>>) -> Option<Box<ListNode>>` first because that's where the main problems are. `merge` will then be easy. Your `list_ptr` should be `mut` and don't forget you can assign to the value referenced by a mutable reference with `*r = value`.

The solution (see `copy3`).

Edit: I hit the wrong reply button by mistake.

1 Like

Yeah I was thinking of implementing `Iterator` and then using the `zip()` function as a possible solution. Still haven't tried that tho. Still might honestly if raw pointers prove to be too annoying.

A post was split to a new topic: Merging Two Sorted Lists