Looking for one weird trick to solve a linked list Leetcode question in safe Rust

help
1

Hello. I'm stuck on how to solve a linked list Leetcode question using safe Rust. This is for leisure and is not part of any assignment that has been given to me. The problem can be found here: https://leetcode.com/problems/reverse-nodes-in-k-group/.

The task is to take a linked list and reverse successive full sequences of k nodes. For instance, for k = 3, 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 would map to 3 - 2 - 1 - 6 - 5 - 4 - 7 - 8.

I feel like I'm halfway there. I have a function which takes a node, takes the first k elements, reverses them, and returns the head of the reversed first k elements, and head of the remaining untouched elements:

struct ListNode {
   val: i32,
   next: Option<Box<ListNode>>
}

// Assume for now that there are at least k values to reverse
fn reverse_k(mut head: Box<ListNode>, k: i32) -> (Box<ListNode>, Option<Box<ListNode>>) {
    if k == 1 {
        return (head, None);
    }

    let mut tail = std::mem::take(&mut head.next).unwrap();

    for _ in 0..(k - 1) {
        let next = tail.next;

        tail.next = Some(head);

        head = tail;

        match next {
            Some(next) => {
                tail = next;
            },
            None => {
                return (head, None);
            }
        }
    }

    (head, Some(tail))
}

If the remaining elements (the second field in the return value of reverse_k) are Some, then we need to apply reverse_k to those elements as well. The question arises of how to string the successive sequences of reversed k elements together.

The only solution I can see for doing this in safe Rust is to traverse the whole accumulated result to the end for each call of reverse_k, which is not great complexity-wise, as you need to traverse the whole accumulated list to get to the end and set its next field.

It would be nice if it were possible to hold references to the end node of the accumulated result (a), and to the end node of each new computed result of reverse_k (b). Each iteration, (a).next would be set to point to the newly reversed sequence of k values, and (a) would then be updated to (b).

The only way I see to do this is to deal with pointers to the contents of the boxes of the end nodes, which would be unsafe.

My question is: Is it possible to solve this problem using safe Rust in O(n) time and O(1) memory (without allocating new nodes)? The crux lies in the question of whether it is possible to return a list node and a reference to its final node.

2

Given your definition of ListNode, you absolutely cannot do this in safe or unsafe Rust. It is undefined behavior to move a Box while holding any pointer to its contents, because Box<T> is (currently) understood by the compiler to be a “unique” pointer exactly like &mut T is. (The usefulness of this design choice is somewhat debated, and a future version of Rust may relax it.)

If you choose to take this route with unsafe code, you will need to use some type other than Box to manage your allocations.

1 Like
3

Are you saying that it is allowed for the contents of a Box to move if the box is moved?

4

Yes, but with a modified approach: Reversing a list satisfies these criteria, so you can build the final list reversed, and then reverse it as a final step before returning.

My solution

5

No, I am saying that moving a Box counts as the same kind of thing as taking an exclusive borrow of the contents of the Box. It has the same implications that you must no longer use any previously-existing aliasing pointers to the contents.

6

Nice solution. Thank you.

7

Just to clarify (I'm not fully understanding): If I call as_mut_ptr on a Box and then move the box, does the pointer become invalid?

8

Testing this particular proposal under Miri:

#![feature(box_as_ptr)]
fn main() {
    let mut b = Box::new(1);
    let ptr = Box::as_mut_ptr(&mut b);
    let bb = b;
    println!("{}", unsafe { *ptr });
}

error: Undefined Behavior: attempting deallocation using <442> at alloc314, but that tag does not exist in the borrow stack for this location
    --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1666:17
     |
1666 |                 self.1.deallocate(From::from(ptr.cast()), layout);
     |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Undefined Behavior occurred here
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <442> was created by a Unique retag at offsets [0x0..0x4]
    --> src/main.rs:5:14
     |
5    |     let bb = b;
     |              ^
help: <442> was later invalidated at offsets [0x0..0x4] by a read access
    --> src/main.rs:6:29
     |
6    |     println!("{}", unsafe { *ptr });
     |                             ^^^^
     = note: BACKTRACE (of the first span):
     = note: inside `<std::boxed::Box<i32> as std::ops::Drop>::drop` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1666:17: 1666:66
     = note: inside `std::ptr::drop_in_place::<std::boxed::Box<i32>> - shim(Some(std::boxed::Box<i32>))` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:799:1: 799:62
note: inside `main`
    --> src/main.rs:7:1
     |
7    | }
     | ^

Interestingly, it isn’t actually saying there is UB on line 6 but that any further use of bb is UB. I think that’s because ptr itself doesn’t have any uniqueness restriction, so ptr doesn’t care about what let bb = b did, but bb does care about ptr having been used. So, according to the Stacked Borrows model (again, all of this is tentative and not yet guaranteed to be in Rust forever, but we have to be conservative and write programs that are definitely not UB now), it's not that “the pointer becomes invalid” but “the Box becomes invalid”. This is largely not a distinction that makes a difference; either way you have to not do it (outside of scenarios involving carefully designed memory leaks or terminating the process before the Box is touched, neither of which helps anything you want to do).

9

Thanks a lot for the explanation.

10

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.