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?