LeetCode 0148 - Sort List

Sort List

Desicription

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

Example 1:

代码语言：javascript复制

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

Example 2:

代码语言：javascript复制

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

Solution

代码语言：javascript复制

/**
 * 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> vec;
        for(auto it = head; it != NULL; it = it->next)
            vec.push_back(it->val);    
        sort(vec.begin(), vec.end());
        int index = 0;
        for(auto it = head; it != NULL; it = it->next) 
            it->val = vec[index  ];
        return head;
    }
};

list sort space time using

0 人点赞