A very simple and straightforward solution


#1

/**

  • Definition for singly-linked list.
  • struct ListNode {
  • int val;
    
  • ListNode *next;
    
  • ListNode(int x) : val(x), next(NULL) {}
    
  • };
    /
    ListNode
    Solution::partition(ListNode* a, int b) {
    if(a==NULL)
    return a;
    ListNode* d=new ListNode(0);
    ListNode* c=d;
    ListNode* head=a;
    while(head!=NULL){
    if(head->val<b){
    ListNode* cur=new ListNode(head->val);
    c->next=cur;
    c=cur;
    }
    head=head->next;
    }
    head=a;
    while(head!=NULL){
    if(head->val>=b){
    ListNode* cur=new ListNode(head->val);
    c->next=cur;
    c=cur;
    }
    head=head->next;
    }
    c->next=NULL;
    return d->next;
    }

#2

just an O(n) space solution


#3

Yes, it is, it isn’t mentinoed in question about usage of space. is it?