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;
}
};
