Untitled

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        queue<int>pq1;
        queue<int>pq2;

        if(!head) return NULL;

        ListNode* trav=head;
        while(trav){
            if(trav->val < x) pq1.push(trav->val);
            else pq2.push(trav->val);
            trav=trav->next;
        }
        ListNode* res=NULL;
        ListNode* t=NULL;
        if(!pq1.empty()){
            res= new ListNode(pq1.front());
            t=res;
            pq1.pop();
        }
        ListNode* mid=NULL;
        if(!pq2.empty()){
            mid = new ListNode(pq2.front());
            pq2.pop();
        }

        while(!pq1.empty()){
            ListNode* tmp =new ListNode(pq1.front());
            pq1.pop();
            t->next=tmp;
            t=tmp;
        }
        if(!res){
            res=mid;
            t=mid;
        }else{
            t->next=mid;
            t=mid;
        }

        while(!pq2.empty()){
            ListNode* tmp =new ListNode(pq2.front());
            pq2.pop();
            t->next=tmp;
            t=tmp;
        }
        if(t){
            t->next=NULL;
        }
        return res;
    }
};