单链表的排序

解题思路

1. 用 vector<ListNode*> 先存储链表中各个节点
2. 使用 sort 对 vector 进行排序
3. 将 vector 中的 ListNode 按顺序串联起来

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

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        vector<ListNode*> nodes;
        ListNode* pNode = head;

        while (pNode) {
            nodes.emplace_back(pNode);
            pNode = pNode->next;
        }

        auto cmp = [](ListNode* a, ListNode* b) -> bool {
            return a->val < b->val;
        };

        sort(nodes.begin(), nodes.end(), cmp);
        for (int i = 0; i < nodes.size() - 1; ++i) {
            nodes[i]->next = nodes[i + 1];
        }
        nodes[nodes.size() - 1]->next = nullptr;
        return nodes[0];
    }
};