public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null)
            return head;
        ListNode node1 = new ListNode(-1), node2 = new ListNode(-1);
        ListNode ptr1 = node1, ptr2 = node2;
        while (head != null) {
            if (head.val < x) {
                ptr1.next = head;
                ptr1 = ptr1.next;
            } else {
                ptr2.next = head;
                ptr2 = ptr2.next;
            }
            head = head.next;
        }
        ptr2.next = null;
        ptr1.next = node2.next;
        return node1.next;
    }