# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        heads = [None, None]
        tails = [None, None]

        cur = head
        idx = 0
        while cur:
            i = idx % 2
            idx += 1
            if heads[i] is None:
                heads[i] = tails[i] = cur
            else:
                tails[i].next = cur
                tails[i] = cur
            cur = cur.next

        if heads[0]:
            tails[0].next = heads[1]
        if tails[1]:
            tails[1].next = None
        return heads[0]