How to deal with recursive data structures in Rust?

[Karsten]

I am currently trying to learn Rust. Therefore I tried to solve challenges I find online and this was mostly successful and surprisingly enjoyable.
But every time the challenge involves any kind of recursive data structure like trees or linked lists it gets messy pretty quickly and I am quite lost.

The worst one was the following where I could not find a solution despite the fact that the C implementation only took me a few minutes.

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Input:

1->2->3->4->5->NULL

Output:

1->3->5->2->4->NULL

(Taken from: https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3331/)

The Rust template given is this:

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

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

pub fn odd_even_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {

}

My C solution for reference:

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* oddEvenList(struct ListNode* head){
    if (head == NULL) return NULL;
    if (head->next == NULL || head->next->next == NULL) return head;
    
    struct ListNode* first_odd = head;
    struct ListNode* last_odd = first_odd;
    struct ListNode* first_even = head->next;
    struct ListNode* last_even = first_even;
    struct ListNode* current = last_even->next;
    int i = 1;
    while (current != NULL) {
        if (i++ % 2 == 0) {
            // even
            last_even->next = current;
            last_even = current;
        } else {
            // odd
            last_odd->next = current;
            last_odd = current;
        }
        current = current->next;
    }
    
    last_even->next = NULL;
    last_odd->next = first_even;
    return first_odd;
}

As you can see my solution needs to mutate the last element in the lists while holding a pointer to the first element and I don't know how to do that in Rust. Can anybody point me in the right direction?

[kornel]

The borrow checker works better for ensuring safe usage of data structures, rather than helping with their internal implementations.

It's expected that lists are awkward to work with. You'll probably need this: https://rust-unofficial.github.io/too-many-lists/

[droundy]

It looks to me like you don't need to hold references to the heads. You can just hold the heads themselves, which ought to enable you to implement your C algorithm essentially without modification.