Skip to content

148.Sort list

难度Medium

刷题内容

原题连接

  • https://leetcode.com/problems/sort-list/

内容描述

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

˼· **- ʱ�临�Ӷ�: O(nlgn)*- �ռ临�Ӷ�: O(n)***

���˼·ͷ͵�˸内容描述�c++�е� sort() �㷨���ֽ������е� val ���δ内容描述��У内容描述�������򡣽����ٰ������е内容描述���м��ɡ�

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> v;
        ListNode* current = head;
        while(current)
        {
            v.push_back(current ->val);
            current = current ->next;
        }
        sort(v.begin(),v.end());
        current = head;
        int i = 0;
        while(current)
        {
            current ->val = v[i++];
            current = current ->next;
        }
        return head;
    }
};


回到顶部