专栏首页aCloudDeveloperLeetcode:148_Sort List | O(nlogn)链表排序 | Medium

Leetcode:148_Sort List | O(nlogn)链表排序 | Medium

题目: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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CPU 虚拟化

    前面 虚拟化技术总览 中从虚拟平台 VMM 的角度,将虚拟化分为 Hypervisor 模型和宿主模型,如果根据虚拟的对象(资源类型)来划分,虚拟化又可以分为计...

    CloudDeveloper
  • LeetCode:21_Merge Two Sorted Lists | 合并两个排序列表 | Easy

    题目:Merge Two Sorted Lists Merge two sorted linked lists and return it as a new l...

    CloudDeveloper
  • Docker 基础技术之 Linux cgroups 详解

    CloudDeveloper
  • 重读《学习JavaScript数据结构与算法-第三版》- 第6章 链表(一)

    本章为重读《学习JavaScript数据结构与算法》的系列文章,该章节主要讲述数据结构-链表,以及实现链表的过程和原理。

    胡哥有话说
  • 数据结构知否知否系列之 — 线性表的顺序与链式存储篇(8000 多字长文)

    线性表是由 n 个数据元素组成的有限序列,也是最基本、最简单、最常用的一种数据结构。

    五月君
  • 6.变量声明与基本类型(Primitive Type)

    本文将会介绍 Java 的基本类型和 Kotlin 的区别。我们知道,Java 的基本类型是 boolean, char, short, int, long, ...

    sickworm
  • 《javascript数据结构和算法》读书笔记(3):链表

    储存多个元素,数组是最常用的。无论何种语言,都实现了数组。但是大多数语言中,数组的长度是固定的。数组修改操作的成本非常高。

    一粒小麦
  • C++获取鼠标位置及全局检测鼠标行为

    1、获取鼠标位置(在屏幕的位置)    CPoint m_mouse;       GetCursorPos(&m_mouse); 2、 屏幕转化为客户端(控件...

    Gxjun
  • SQL 差集计算的例子

    一个会写诗的程序员
  • Unity-Optimizing Unity UI(UGUI优化)02 Unity UI性能分析工具

    拓展工具提供了方法级CPU毫秒级性能分析的解决方案,包括draw-call的细节和shader的性能分析。注意XCode帧调试和仪器只能在IL2CPP构建在苹果...

    祝你万事顺利

扫码关注云+社区

领取腾讯云代金券