单链表的排序

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        vector<ListNode*> v;
        while (head != nullptr) {
            v.emplace_back(head);
            head = head->next;
        }
        auto cmp = [](const ListNode* l1, const ListNode* l2) {
            return l1->val < l2->val;
        };
        sort(v.begin(), v.end(), cmp);

        for (int i = 0; i < v.size() - 1; i++) {
            v[i]->next = v[i + 1];
        }
        // 注意要把最后一个元素的next赋值为nullptr，否则会形成环
        v[v.size() - 1]->next = nullptr;
        return v[0];
    }
};