public ListNode partition(ListNode head, int x) {
        if (head == null || head.next ==null) {
            return head;
        }
        
        ListNode newtail = head, newmiddle = head;
        ListNode it = head.next;
        head.next = null;
        while (it != null) {
            ListNode tmp = it.next;
            if (it.val >= x) {
                newtail.next = it;
                it.next = null;
            }
            else {
                it.next = newmiddle.next;
                newmiddle = it;
            }
            it = tmp;
        }
        return head;
    }