LeetCode - The World's Leading Online Programming Learning Platform

Intuition

• Three initial pointers: one for the odd numbers (head), one for the even numbers (head.next), and the third for the first even number (head.next)
• Continue moving the odd pointer and the even pointer until one of them reaches null

Approach

when the list length is even (yellow pinter = odd; red pointer = even)

when the list length is odd

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Code

# 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]:
        # len = 0
        if head is None:
            return None
        # len = 1
        if head.next is None:
            return head
        # len >= 2
        odd = head
        even = head.next
        even_head = head.next
        while odd and even:
            if even.next is not None:
                odd.next = even.next
                odd = odd.next
            else:
                odd.next = even_head
                break
            if odd.next is not None:
                even.next = odd.next
                even = even.next
            else:
                even.next = None
                odd.next = even_head
                break
        return head