题解 | 链表排序

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

#include <algorithm>
#include <stack>
#include <vector>
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortList(ListNode* head) 
    {
        queue<int>bucket[20];
        ListNode *recode=head;
        if(recode==nullptr)
        return head;
        int max=head->val;
        while (recode!=nullptr) 
        {if(recode->val>max)
          max=recode->val;
          recode=recode->next;
        }//找最大数
        for(int exp=1;max/exp>0;exp*=10)
        {
            recode=head;
            while (recode!=nullptr)
            {
                int idx=(recode->val/exp)%10+10;//考虑到负数，增加偏移量
               bucket[idx].push(recode->val);
               recode=recode->next;
            }//入桶
            recode=head;
            for(int j=0;j<20;j++)
            {
                while (!bucket[j].empty())
                {
                 recode->val=bucket[j].front();
                 recode=recode->next;
                 bucket[j].pop();
                }
            }//出通
        }
        return head;
    }
};