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.

4 posts - 3 participants

Read full topic