题目简介

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

模板

/**
 * 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) {

    }
};

思路

转换为vector动态数组，使用排序算法进行排序，然后用排序后的结果替换掉原来的链表。（无需考虑链表空间的拓展，因为排序后的元素数量必和原链表中的元素数量相同）

在转换的过程中要注意验证空指针。

代码

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> a;
        ListNode* b;
        b = head;
        while (b!=nullptr && b->next != nullptr)
        {
            a.push_back(b->val);
            b = b->next;
        }
        if (b != nullptr)
        {
            a.push_back(b->val);
        }
        sort(a.begin(), a.end());
        b = head;
        for (int cptime = 0; b!=nullptr && b->next != nullptr;cptime++ )
        {
            b->val = a[cptime];
            b = b->next;
        }
        if (b != nullptr)
        {
            b->val = a[a.size() - 1];
        }
        return head;
    }
};