Description
Sort a linked list in O(n log n) time using constant space complexity.
在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。
Examples
Input: -1->5->3->4->0
Output: -1->0->3->4->5
Answer
Using merge sort to sort the linked list. Using quicksort is also available.
Time Complexity
O(nlogn)
Code
C++
class Solution {
public:
ListNode* split(ListNode* head, int cnt){
if(!head) return nullptr;
while(--cnt && head)
head = head->next;
ListNode* tail = head->next;
head->next = nullptr;
return tail;
}
ListNode* merge(ListNode* left, ListNode* right, ListNode* head){
ListNode* cur = head;
while(left || right)
{
if(!right || (left->val < right->val))
{
cur->next = left;
cur = left;
left = left->next;
}
else
{
cur->next = right;
cur = right;
right = right->next;
}
}
return cur;
}
int getLen(ListNode* head){
int len = 0;
while(head)
{
++len;
head = head->next;
}
return len;
}
ListNode* sortList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* cur, *left, *right, *tail;
ListNode dummy(0);
dummy.next = head;
int cnt = getLen(head);
for(int i = 1; i < cnt; i <<= 1)
{
cur = dummy.next;
tail = &dummy;
while(cur){
left = cur;
right = split(left, i);
cur = split(right, i);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
};
