from utils.listNode import ListNode

class Solution:
    # time: O(N)
    # space: O(1)
    def partition(self, head, pivot):
        if not head:
            return head
        
        s_head = smaller = ListNode(None)
        g_head = greater = ListNode(None)
        node = head

        while node:
            if node.value < pivot:
                smaller.next = node
                smaller = node
            else:
                greater.next = node
                greater = node
            
            node = node.next
        
        greater.next = None
        smaller.next = g_head.next

        return s_head.next

one = ListNode(1)
two = ListNode(4)
three = ListNode(3)
four = ListNode(2)
five = ListNode(5)
six = ListNode(2)

one.next = two
two.next = three
three.next = four
four.next = five
five.next = six

print(one)

solution = Solution()
print(solution.partition(one, 3))