排序链表

问题描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list

思路

• 遍历链表，将链表存在一个int类型的vector中。
• 对链表进行排序。
• 根据vector重新建立一个链表。

题解

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        ListNode *p = head;
        vector<int> vec;
        while (p != nullptr) {
            vec.push_back(p->val);
            p = p->next;
        }
        if(vec.size()==0)
            return nullptr;
        sort(vec.begin(),vec.end());
        ListNode *q = nullptr;
        ListNode *ret;
        for (int i = 0; i < vec.size(); i++) {
            if (q == nullptr) {
                q = new ListNode(vec[i]);
                ret=q;

            } else {
                q->next = new ListNode(vec[i]);
                q = q->next;
            }
        }
        return ret;
    }
};