92ms c++


  • 0
    B
    
    
    class Solution {
    public:
        struct Node {
            int val;
            int cnt;
            Node* next;
            Node(int x) : val(x),cnt(1),next(NULL) {}
        };
    
        ListNode* insertionSortList(ListNode* head) {
            if (head==NULL) return NULL;
            Node* shead = new Node(head->val);
            Node* sp;
            Node* tmpsp;
            ListNode* p=head->next;
            while (p!=NULL)
            {
    
                if (p->val < shead->val)
                {
                    Node* node2 = new Node(p->val);
                    node2->next=shead;
                    shead=node2;
                    p=p->next;
                    continue;
                }
                sp = shead;
                tmpsp = sp;
                while ((sp!=NULL)&&(sp->val < p->val))
                {
                    tmpsp=sp;
                    sp=sp->next;
                }
                if (tmpsp->val == p->val)
                    tmpsp->cnt = tmpsp->cnt+1;
                else
                {
                    Node* node = new Node(p->val);
                    node->next=tmpsp->next;
                    tmpsp->next=node;
                }
                p=p->next;
            }
            ListNode* h = new ListNode(0);
            ListNode* x = h;
            while (shead!=NULL)
            {
                for(int i=1;i<=shead->cnt;i++)
                {
                    ListNode* n = new ListNode(shead->val);
                    x->next = n;
                    x=x->next;
                }
                shead = shead->next;
            }
            return h->next;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.