题目描述

在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
Sort a linked list in O(n log n) time using constant space complexity.
示例1

输入

复制

{3,2,4}

输出

复制

{2,3,4}

class Solution {
public:
    ListNode* findMiddle(ListNode* head){
        ListNode* chaser = head;
        ListNode* runner = head->next;
        while(runner != NULL && runner->next != NULL){
            chaser = chaser->next;
            runner = runner->next->next;
        }
        return chaser;
    }
     
 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL){
            return l2;
        }
        if(l2 == NULL){
            return l1;
        }
        ListNode* dummy = new ListNode(0);
        ListNode* head = dummy;
        while(l1 != NULL && l2 != NULL){
            if(l1->val > l2->val){
                head->next = l2;
                l2 = l2->next;
            }
            else{
                head->next = l1;
                l1 = l1->next;
            }
            head = head->next;
        }
        if(l1 == NULL){
            head ->next = l2;
        }
        if(l2 == NULL){
            head->next = l1;
        }
        return dummy->next;
    }
     
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head ->next == NULL){
            return head;
        }
        ListNode* middle = findMiddle(head);
        ListNode* right = sortList(middle->next);
        middle -> next = NULL;
        ListNode* left = sortList(head);
        return mergeTwoLists(left, right);
    }
};

最新文章

  1. CodeForces 515C. Drazil and Factorial
  2. Windows Server+AMD GPU+HDMI时_黑边_不铺满问题的解决办法
  3. Swift3.0语言教程字符串大小写转化
  4. python中threading模块详解（一）
  5. 在Android Studio中使用shareSDK进行社会化分享（图文教程）
  6. Bootstrap3.0学习第十三轮(导航条)
  7. Ubuntu下中文显示乱码
  8. 解决：Eclipse调试的时候报错'Launching XXX' has encountered a problem. Cannot connect to VM.
  9. Javascript this 解析
  10. Initializer block.
  11. 温习H3C S5500的VLAN配置
  12. flvplayer.swf flv视频播放器使用方法
  13. Netbeans搭建Android环境
  14. ES 6 : 字符串的扩展
  15. 收藏清单: python测试框架最全资源汇总
  16. nginx+keepalived高可用及双主模式
  17. Python学习笔记-数字类型
  18. A Bug's Life(向量偏移)
  19. 【Spring学习笔记-MVC-15】Spring MVC之异常处理
  20. oracle杀掉执行的死循环存储过程

热门文章

  1. 实时，异步网页使用jTable, SignalR和ASP。NET MVC
  2. 搭建go-stress-testing压力测试
  3. MySQL - 常用三种数据库存储引擎
  4. Struts2 学习记录-第一天
  5. Flask之WTF
  6. C/C++编程日记：用C语言实现的简单Web服务器(Linux)，全代码分享！
  7. centos8安装RabbitMQ
  8. centos8安装fastdfs6.06集群方式一之：软件下载与安装
  9. gti 常用命令
  10. 说明资源路径位置类型无法解析The type javax.servlet.http.HttpServletResponse cannot be resolved.