Reagrupa la lista enlazada

La función recibe una lista enlazada node1->node2->node3->node4->node5->None. Vuelve a enlazar la lista original de modo que primero todos los nodos impares y luego todos los nodos pares queden enlazados entre sí, preservando el orden original de aparición. La lista modificada debe ser: node1->node3->node5->node2->node4->None. La clase de lista enlazada está definida en la pestaña Tests:

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

La clase tiene el campo .val y la referencia al siguiente nodo .next. La función recibe la referencia a la cabeza de la lista, reorganiza los enlaces internos y devuelve la referencia a la cabeza.

Ejemplos

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]

Notas

Es preferible volver a enlazar la lista en el mismo lugar, sin crear nodos nuevos, aunque también pueden superar las pruebas otras soluciones menos eficientes.