Odd Even Linked List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

/*
Logic:
break the linked list into two halves ,one for the odd position and one for even positions.
then join both of them.
*/
class Solution:
    def oddEvenList(self, head):
        if not head or not head.next:
            return head

        cur = head.next.next
        odd_head = odd_tail = head
        even_head = even_tail = head.next

        even_tail.next = None  # 🔥 break original chain
        odd_tail.next = None
        is_odd = True #because it is starting form the 3rd node

        while cur:
            next_node = cur.next
            cur.next = None

            if is_odd:
                odd_tail.next = cur
                odd_tail = cur
            else:
                even_tail.next = cur
                even_tail = cur

            is_odd = not is_odd
            cur = next_node

        odd_tail.next = even_head

        return odd_head