[LeetCode] Odd Even Linked List

 

 

Problem

 

 

 

---

 

Solution

 

# 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]:
        odd = dummy = ListNode(0)
        even = dummy2 = ListNode(0)
        
        # group odds and evens, and put the evens after odds
        while head:
            odd.next = head
            even.next = head.next
            odd = odd.next
            even = even.next
            
            head = head.next.next if even else None
        
        odd.next = dummy2.next
        
        return dummy.next

Time Complexity

O(N)

 

 

Space Complexity

O(1)

I thought the solution might not be constant space if I make two new nodes for odd and even pointers. However, it is constant space because the space used for 2 dummy ListNodes does not change no matter what the input is.