当前位置: 首页 > news >正文

[LeetCode] Sort List

Sort a linked list in O(n log n) time using constant space complexity.

  • 解题思路
    可以利用归并排序解决该问题。普通的归并排序算法时间复杂度为O(nlogn),空间复杂度为O(n),因为需要建立两个数组来存储原来数组的值,这两个数组的长度加起来恰好为原数组的长度。但是对于链表可以省去复制两个已经排好序的数组的操作,从而使空间复杂度达到O(1)。

  • 实现代码

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/16 21:46
    *  @Status   : Accepted
    *  @Runtime  : 79 ms
******************************************************************/
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}

};

class Solution {
public:
    ListNode * getMiddleOfList(ListNode *head)
    {
        ListNode *p = head;
        ListNode *q = head;
        while(q->next != NULL && q->next->next != NULL)
        {
            p = p->next;
            q = q->next->next;
        }

        return p;
    }

    ListNode *mergeList(ListNode *head1, ListNode *head2)
    {
        ListNode *merge = new ListNode(-1);
        ListNode *tmp = merge;
        while(head1 != NULL && head2 != NULL)
        {
            if (head1->val <= head2->val)
            {
                tmp->next = head1;
                head1 = head1->next;
            }
            else
            {
                tmp->next = head2;
                head2 = head2->next;
            }
            tmp = tmp->next;
        }

        if(head1 == NULL)
        {
            tmp->next = head2;
        }
        else
        {
            tmp->next = head1;
        }

        return merge->next;
    }

    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode *middle = getMiddleOfList(head);
        ListNode *next = middle->next;
        middle->next = NULL;
        return mergeList(sortList(head), sortList(next));
    }
};

void print(ListNode *head)
{
    ListNode *tmp = head;
    while(tmp)
    {
        cout<<tmp->val<<" ";
        tmp = tmp->next;
    }
    cout<<endl;
}

int main()
{
    ListNode* head = new ListNode(-1);
    ListNode* node1 = new ListNode(8);
    head->next = node1;
    ListNode* node2 = new ListNode(5);
    node1->next = node2;
    ListNode* node3 = new ListNode(9);
    node2->next = node3;
    ListNode* node4 = new ListNode(0);
    node3->next = node4;
    ListNode* node5 = new ListNode(1);
    node4->next = node5;
    ListNode* node6 = new ListNode(3);
    node5->next = node6;
    ListNode* node7= new ListNode(6);
    node6->next = node7;
    ListNode* node8 = new ListNode(4);
    node7->next = node8;
    print(head);

    Solution s;
    s.sortList(head);
    print(head);
}

相关文章:

  • 等待超时,请打开设备管理器查看苹果驱动是否正常!
  • 【POJ】2096 Collecting Bugs
  • 【Linux】linux经常使用基本命令
  • [JAVA设计模式]第二部分:创建模式
  • nyoj86-找球号(一) 【set 二分查找 hash】
  • 关于数组集合之间的转换
  • Android Bitmap和Canvas学习笔记
  • 12 redis之aof日志持久化
  • Intersection of Two Linked Lists(链表)
  • FastDfs 文件系统迁移
  • js实现页面重定向
  • 纪念逝去的岁月——C/C++字符串反转
  • 【SICP练习】92 练习2.65
  • 第十七章——配置SQLServer(1)——为SQLServer配置更多的处理器
  • mysql全文索引____ft_min_word_len
  • [译]如何构建服务器端web组件,为何要构建?
  • create-react-app项目添加less配置
  • Docker下部署自己的LNMP工作环境
  • HTTP中GET与POST的区别 99%的错误认识
  • mysql 数据库四种事务隔离级别
  • mysql_config not found
  • opencv python Meanshift 和 Camshift
  • 大数据与云计算学习:数据分析(二)
  • 大整数乘法-表格法
  • 工程优化暨babel升级小记
  • 基于Dubbo+ZooKeeper的分布式服务的实现
  • 理解IaaS, PaaS, SaaS等云模型 (Cloud Models)
  • 前端_面试
  • 微信小程序:实现悬浮返回和分享按钮
  • 赢得Docker挑战最佳实践
  • 原生JS动态加载JS、CSS文件及代码脚本
  • 深度学习之轻量级神经网络在TWS蓝牙音频处理器上的部署
  • Java总结 - String - 这篇请使劲喷我
  • 浅谈sql中的in与not in,exists与not exists的区别
  • (13)Hive调优——动态分区导致的小文件问题
  • (C#)if (this == null)?你在逗我,this 怎么可能为 null!用 IL 编译和反编译看穿一切
  • (非本人原创)史记·柴静列传(r4笔记第65天)
  • (附源码)ssm基于jsp的在线点餐系统 毕业设计 111016
  • (附源码)计算机毕业设计ssm本地美食推荐平台
  • (实战)静默dbca安装创建数据库 --参数说明+举例
  • (原)Matlab的svmtrain和svmclassify
  • (转)socket Aio demo
  • (转)全文检索技术学习(三)——Lucene支持中文分词
  • ***测试-HTTP方法
  • .Net接口调试与案例
  • .net实现客户区延伸至至非客户区
  • :=
  • @JSONField或@JsonProperty注解使用
  • @JsonFormat与@DateTimeFormat注解的使用
  • []我的函数库
  • [Android View] 可绘制形状 (Shape Xml)
  • [caffe(二)]Python加载训练caffe模型并进行测试1
  • [CCIE历程]CCIE # 20604
  • [Gamma]阶段测试报告
  • [GXYCTF2019]禁止套娃