/**
 * 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) {
        if(head==NULL)
            return NULL;
        vector<int> res;

        while(head){
            res.push_back(head->val);
            head = head->next;
        }
        sort(res.begin(), res.end());  // 排序
        ListNode* L = new ListNode();
        ListNode* p = L;
        for(int i = 0; i < res.size(); i++){  // 生成新节点，重建链表
            ListNode* tmp = new ListNode(res[i]);
            p->next = tmp;
            p = p->next;
        }
        return L->next;
    }
};