//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* sortList(ListNode* head)

    {

        ListNode* dummyhead=new ListNode(0,head);

        ListNode* p=dummyhead;

        while(p->next!=nullptr)

        {

            p->next->val+=100000;

            p=p->next;

        }

        vector<queue<ListNode*>>vec(10); // 按 0～9 分组

        for(int i=1;i<=100000;i*=10) // 这里是 6 位数，共 6 趟

        {

            int flag=0;

            while(dummyhead->next!=nullptr)

            {

                if(dummyhead->next->val/(i*10)!=0)

                    flag=1;

                vec[dummyhead->next->val/i%10].push(dummyhead->next);

                dummyhead->next=dummyhead->next->next;

            }

            ListNode* p=dummyhead;

            for(int j=0;j<10;++j) // 将每个组节点连接起来

            {

                while(!vec[j].empty())

                {

                    vec[j].front()->next=p->next;

                    p->next=vec[j].front();

                    p=p->next;

                    vec[j].pop();

                }

            }

            if(flag==0)

                break;

        }

        p=dummyhead;

        while(p->next!=nullptr)

        {

            p->next->val-=100000;

            p=p->next;

        }

        ListNode* ret=dummyhead->next;

        delete dummyhead;

        return ret;

    }

};