题解 | #单链表的排序#

先把单链表拆分成结点，并将这些结点保存到vector中，自定义排序lambda对象，对vector进行sort，最后遍历vector把排序好的结点链接起来。注意拆分链表后，每个结点的next为空。

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        vector<ListNode*> vec{};
        while(head!=nullptr){
            auto cur=head;
            head=head->next;
            cur->next=nullptr;
            vec.push_back(cur);
        }
        auto cmp=[](ListNode* node1,ListNode* node2){
            return node1->val < node2->val;
        };
        sort(vec.begin(),vec.end(),cmp);
        ListNode* dummy_head=new ListNode{INT_MIN};
        auto cur=dummy_head;
        for(int i=0;i<vec.size();i++){
            cur->next=vec[i];
            cur=cur->next;
        }
        return dummy_head->next;
    }
};