Partition List

    ListNode *partition(ListNode *head, int x) {
        ListNode dummy(x-1);dummy.next=head;
        ListNode *cur=&dummy,*prev=&dummy;
        while(cur->next){
            if(cur->next->val>=x){
                cur=cur->next;
            }
            else{
                if(prev==cur){
                    prev=prev->next;
                    cur=cur->next;
                }else{
                    ListNode*tnode=cur->next;
                    cur->next=tnode->next;
                    tnode->next=prev->next;
                    prev->next=tnode;
                    prev=tnode;
                }
            }
        }
        return dummy.next;
    }

//second flavor, from anniekim
ListNode *partition(ListNode *head, int x) {
    ListNode leftdummy(-1);
    ListNode rightdummy(-1);
    ListNode * lhead = &leftdummy;
    ListNode * rhead = &rightdummy;
    for(ListNode*cur = head; cur; cur=cur->next){
        if(cur->val<x){
            lhead->next = cur;
            lhead = lhead->next;
        }else{
            rhead->next = cur;
            rhead = rhead->next;
        }
    }
    lhead->next = rightdummy.next;
    rhead->next = nullptr;
    return leftdummy.next;
}