Reorganize a lista encadeada

A função recebe uma lista encadeada node1->node2->node3->node4->node5->None. Religue a lista original de modo que primeiro todos os nós ímpares e depois todos os nós pares fiquem encadeados, preservando a ordem original de aparição. A lista modificada deve ser: node1->node3->node5->node2->node4->None. A classe da lista encadeada está definida na aba Tests:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

A classe tem o campo .val e a referência para o próximo nó .next. A função recebe a referência para o início da lista, reorganiza os links internos e retorna a referência para o início.

Exemplos

lst = [12, 21]
ll = ListNode(lst[0])
ll.add_data(lst[1:])
odd_even_list(ll).get_data() ➞ [12, 21]

lst = [8, 7, 6]
ll = ListNode(lst[0])
ll.add_data(lst[1:])
odd_even_list(ll).get_data() ➞ [8, 6, 7]

lst = [1, 2, 3, 4, 5, 6]
ll = ListNode(lst[0])
ll.add_data(lst[1:])
odd_even_list(ll).get_data() ➞ [1, 3, 5, 2, 4, 6]

Observações

É preferível religar a lista no próprio lugar, sem criar novos nós, embora outras soluções menos eficientes também possam passar nos testes.