首页 > 代码库 > Leetcode：Sort List
Leetcode：Sort List
题目：Sort List
Sort a linked list in O(n log n) time using constant space complexity
看题目有两个要求：1）时间复杂度为O（nlogn）;2）空间复杂度为常数，即不能增设额外的空间。
满足这样要求的排序算法，我们首先想到快排，合并排序和堆排序。我们来分析下几种排序算法对时间和空间复杂度的要求，堆排序实现上过于繁琐，我们不做考虑。快排的最坏的时间复杂度是O(n^2)，平均复杂度为O(nlgn)，如果按照题目的严格要求显然快排是不满足的，而且快排的实现引入了递归操作，递归调用的栈空间严格意义上说也是额外空间。另外值得注意的一点是：链表不像数组一样，可以随机访问元素，链表必须顺序访问，所以一般的递归操作很难实现，虽然也可以实现哈，见该文：递归实现链表排序。对于归并排序，我们知道需要O(n)的空间复杂度，即需要一个临时数组来存放排好序的元素，显然也合理，但那是针对的是数组，对于链表，归并排序的空间复杂度为in-place sort，即不需要额外空间就可以完成。另外，归并排序还有一个比较好的优势是其稳定性。所以，对于本题的解法，我们首选归并排序。
归并排序有多种方式，总的来说有三种，1）递归；2）非递归；3）自然合并；详见本文：归并排序的三种实现方法。对于链表，采用非递归的方式更为高效，用以下的一幅图来说明非递归的方式：
将两两子列表进行合并组合，达到排序的目的。本题的代码如下，参考上文实现的。
1 ListNode *sortList(ListNode *head) 2 { 3 assert(NULL != head); 4 if (NULL == head) 5 return NULL; 6 7 ListNode *p = head; 8 int len = 0; //get the length of link 9 while (NULL != p) {10 p = p->next;11 len ++;12 }13 14 ListNode *temp = new ListNode(0);15 temp->next = head;16 17 int interval = 1; //合并子列表的长度18 for (; interval <= len; interval *= 2) {19 ListNode *pre = temp;20 ListNode *first = temp->next; //两段子列表的起始位置21 ListNode *second = temp->next;22 23 while (NULL != first || NULL != second) {24 int i = 0;25 while (i < interval && NULL != second) {26 second = second->next; //将second移到第二段子列表的起始处27 i ++;28 }29 30 int fvisit = 0, svisit = 0; //访问子列表的的次数<interval，保证列表中的元素全部能被访问31 while (fvisit < interval && svisit < interval && NULL != first && NULL != second) {32 if (first->val < second->val) {33 pre->next = first;34 pre = first;35 first = first->next;36 fvisit ++;37 }38 else {39 pre->next = second;40 pre = second;41 second = second->next;42 svisit ++;43 }44 }45 while (fvisit < interval && NULL != first) {46 pre->next = first;47 pre = first;48 first = first->next;49 fvisit ++;50 }51 while (svisit < interval && NULL != second) {52 pre->next = second;53 pre = second;54 second = second->next;55 svisit ++;56 }57 pre->next = second;58 first = second;59 }60 }61 ListNode *retResult = temp->next;62 delete temp;63 temp = NULL;64 return retResult;65 }
Leetcode：Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。