LeetCode 406. 根据身高重建队列-526互联

class Solution {
public:
    struct node
    {
        int val;
        int pre;
        node* next;
        node(int a,int b,node* c)
        {
            val=a;
            pre=b;
            next=c;
        }
    };
    void insert(node* &head,int h,int pre)
    {
        auto p=head;
        int cnt=0;
        while(p->next&&cnt<pre)
        {
            if(p->next->val>=h)   cnt++;
            p=p->next;
        }
        p->next=new node(h,pre,p->next);   
    }
    static bool cmp(vector<int> &a, vector<int> &b) 
    {
        if(a[0]==b[0])  return a[1]<b[1];//要求少的先排
        else return a[0]>b[0];//高的先排
    };
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        auto head=new node(-1,-1,NULL);
    sort(people.begin(), people.end(), cmp);
        vector<vector<int>> res;
        for(auto q:people)
        {
            int h=q[0],pre=q[1];
            insert(head,h,pre);
        }
        for(auto p=head->next;p;p=p->next)
            res.push_back({p->val,p->pre});
        return res;
    }
};