328. Odd Even Linked List

[fockspaces]

1. double node, odd and even respectively
2. record the even_head
3. once found both have next point node, keep advancing
4. finally, connect the odd tail and even_head
5. return head

# 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]:
        if not head or not head.next:
            return head
        odd, even = head, head.next
        even_head = even
        while odd.next and even.next:
            next_odd = odd.next.next
            next_even = even.next.next
            odd.next, even.next = next_odd, next_even
            odd, even = odd.next, even.next
        odd.next = even_head
        return head