Zipping together two linked lists


#1

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
  --> .\linked-list-zip.rs:36:25
   |
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
  --> .\linked-list-zip.rs:39:25
   |
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`
  --> .\linked-list-zip.rs:39:25
   |
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
  --> .\linked-list-zip.rs:39:41
   |
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
  --> .\linked-list-zip.rs:43:25
   |
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
  --> .\linked-list-zip.rs:52:25
   |
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.
For more information about an error, try `rustc --explain E0384`.

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 :confused:


#2

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.


#3

So what do you suggest I do instead?


#4

In general, the borrow checker doesn’t understand linked lists: https://cglab.ca/~abeinges/blah/too-many-lists/book/ 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.


#5

Thank you!


#6

That’s pretty much the story of life with Linked Lists :sweat_smile:

As an idea for a similar-but-different challenge in rust, consider making an iterator that lazily merges two sorted iterators.


#7

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.


#8

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.