//100
class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null || head.next == null) return head;

        ListNode first_head = new ListNode(-1);
        ListNode first = first_head;
        ListNode second_head = new ListNode(-1);
        ListNode second = second_head;

        while(head != null){
            if(head.val >= x){
                second.next = head;
                second = second.next;
            } else {
                first.next = head;
                first = first.next;
            }
            head = head.next;
        }

        second.next = null;
        first.next = second_head.next;
        first_head = first_head.next;

        return first_head;
    }
}