题解 | 链表分割

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        queue<ListNode*>Q1,Q2;
        ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                Q1.push(cur);
            }
            else {
                Q2.push(cur);
            }
            cur=cur->next;
        }
        ListNode* var=new ListNode(0);
        ListNode* cur1=var;
        while(!Q1.empty())
        {
            cur1->next=Q1.front();Q1.pop();
            cur1=cur1->next;
        }
        while(!Q2.empty())
        {
            cur1->next=Q2.front();Q2.pop();
            cur1=cur1->next;
        }
        cur1->next=nullptr;
        cur1=var->next;
        delete var;
        return cur1;

    }
};