對于連結清單的排序問題,想找一種時間複雜度為O(nlogn),空間複雜度O(1)的算法。該問題源自于Leetcode,Sort a linked list in O(n log n) time using constant space complexity.
首先想到了歸并排序,因為連結清單的歸并不需要輔助空間。
思路:和數組的二路歸并基本一緻。
所不同的是:
1、要周遊一遍才能找到中間位置。
2、首尾位置都要記下來,因為連結清單不是自然相鄰的。是以排序後傳回時要傳回首尾結點的新指針。
3、周遊查找時也要注意連結清單結尾判定可能不再是NULL。
/**
* 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) {
if(head == NULL)
return NULL;
ListNode *end = head;
while(end->next != NULL)
end = end->next;
sort(head, end);
return head;
}
void sort(ListNode* &left, ListNode* &right)
{
if(left == right)
return;
//尋找中間位置
ListNode *p1, *p2;
p1 = p2 = left;
while(p2 != right && p2->next != right)
{
p1 = p1->next;
p2 = p2->next->next;
}
p2 = p1->next;
//遞歸分治
sort(left, p1);
sort(p2, right);
p1->next = NULL;
right->next = NULL;
//歸并
ListNode *new_start,*new_end, *tmp;
if(left->val < p2->val)
{
new_start = left;
left = left->next;
}
else
{
new_start = p2;
p2 = p2->next;
}
tmp = new_start;
while(left != NULL && p2 != NULL)
{
if(left->val < p2->val)
{
tmp->next = left;
tmp = left;
left = left->next;
}
else
{
tmp->next = p2;
tmp = p2;
p2 = p2->next;
}
}
if(left != NULL)
{
tmp->next = left;
new_end = p1;
}
else
{
tmp->next = p2;
new_end = right;
}
//傳回新連結清單頭和連結清單尾
left = new_start;
right = new_end;
right->next = NULL;
}
};
PS:連結清單的排序用快速排序應該也可以做到。