题解 | #单链表的排序#

// 合并的思路：先用容器将节点装起来，然后用sort函数进行排序，最后用指针指向容器首元素，将容器内的节点全部串起来，最后尾节点补上nullptr即可，返回指向容器首元素的指针

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        vector<ListNode*> vec;
        ListNode* cur = head;
        while(cur) {
            vec.push_back(cur);
            cur = cur->next;
        }
        sort(vec.begin(), vec.end(), [](const ListNode* l1, const ListNode* l2) { return l1->val <= l2->val; });

        ListNode* newHead = vec[0];
        int i = 0;
        for(; i<vec.size()-1; i++) {
            vec[i]->next = vec[i+1];
        }
        vec[i]->next = nullptr;

        return newHead;
    }
};