public ListNode partition(ListNode head, int x) {

        ListNode p1 = null, p2 = head, p2Prev = null;

        while( p2 != null ) {
            if( p2.val < x ) {
                if( p1 == p2Prev ) {
                    p1 = p2;
                    p2 = p2.next;
                    p2Prev = p1;
                } else {
                    p2Prev.next = p2.next;
                    if( p1 == null ) {
                        p2.next = head;
                        head = p2;
                    } else {
                        p2.next = p1.next;
                        p1.next = p2;
                    }
                    p1 = p2;
                    p2 = p2Prev.next;
                }
            } else {
                p2Prev = p2;
                p2 = p2.next;
            }
        }
        return head;
    }