148.排序链表
发布日期:2021-10-12 21:31:50 浏览次数:1 分类:技术文章

本文共 1560 字,大约阅读时间需要 5 分钟。

依然是一道我做不出来的题。。像这种题只有这次看题解看懂了下次再自己重做一次来巩固了。对我来说这道题好像有点超出我的范围了,不过经过一个小时的看题解的过程,,我终于是写出来了。。。惨。。

这道题不仅是归并排序,而且还规定了常数级空间。而我归并排序以前只是有模糊的记忆,直到今天才真正学了归并排序,而且,这里不能用递归,不然就不是常数级空间了。

首先,要理解的是什么是归并排序,就是这样的,假如有n个数,你第一次排序,把n个数分成n份,然后两份一组排序,两份一组排序,都排好了后现在就是n/2组,每一组都是排好序的,虽然后来,下一次就是分成n/2份,每份两个元素,再来两份一组两份一组的排序,知道最后只分成了1份,那么这个数组就是通过归并排序排好的了。思路应该很容易理解,只是代码的实现就不是这么容易了,因为这里是链表!不是数组。。。

cut声明为表示每份的元素个数,每一次大循环后cut的值变为原来的两倍。归并排序是每两份一组,每两份一组的进行排序的,知道链表为nil。所以首先声明h1,来表示第一组,声明i=cut,h1每向后next一下,i--,退出条件就是i<=0 || h1 == nil这里要注意的是假如此时退出来了而i是大于0的,那么就跳出这次循环,说明后面已经没有h2能够和他进行合并操作了。假如<=0,那么就继续选择出第二组,第二组就没有i的问题,就算i>0,照样可以进行归并排序。不过我们要声明一个变量v2=cut-i,来表示第二组的元素个数,因为有可能第二组并没有那么多元素。当这都准备好了后就可开始进行合并了,合并完成后将还不为nil的链表那组直接加在总链表的后面,当然,这个时候还要更新pre.next为当前h,因为这一组大循环还没有结束,下一次就是另外两组元素来进行了。最后我们返回res.next就是排好序的链表。

我确实觉得这道题的难度有点大了,假如面试的时候碰到这道题我也只有认了。。。

代码如下:

/**

 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    length,cut := 0,1
    res := &ListNode{}
    res.Next = head
    h := head
    
    for h != nil {
        h = h.Next
        length++
    }

    for cut < length {

        pre := res
        h := res.Next
        for h != nil{
            i := cut
            h1 := h
            for i > 0 && h != nil {
                i--
                h = h.Next
            }
            if i >0 {
                break
            }
            i = cut
            h2 := h
            for i>0 && h != nil {
                i--
                h = h.Next
            }
            v1,v2 := cut,cut-i
            for v1 >0 && v2 > 0 {
                if h1.Val < h2.Val {
                    pre.Next = h1
                    h1 = h1.Next
                    v1--
                }else{
                    pre.Next = h2
                    h2 = h2.Next
                    v2--
                }
                pre = pre.Next
            }
            if v1==0 {
                pre.Next = h2
            }else{
                pre.Next = h1
            }
            for v1 > 0 || v2 > 0 {
                pre = pre.Next
                v1--
                v2--
            }
            pre.Next = h
        }
        cut = cut * 2
    }

    return res.Next

}

 

 

java版:

   还是感觉难。。。

  

 

转载地址:https://blog.csdn.net/qq_40058686/article/details/104426175 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:152.乘积最大子序列
下一篇:141.环形链表

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月13日 15时35分06秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

MATLAB中GUI界面弹出菜单的使用,Matlab GUIDE使用说明(Matlab GUI界面) 2019-04-21
win iis对比apache php,服务器Apache与IIS的区别 2019-04-21
怎样用xampp测试php环境变量,使用xampp配置php运行环境的方法 2019-04-21
qq互联php教程,thinkphp5怎么整合qq互联登录教程 2019-04-21
Java怎么比较4数字大小,怎么判断四个数不成比例-判断4个数值相等-数学-古残夷同学... 2019-04-21
mysql建立索引 性能测试_MySQL分区和索引性能测试 2019-04-21
数据结构java实验 刘小晶_数据结构实例解析与实验指导:Java语言描述 2019-04-21
java实现 k nn算法_java-C中的k-NN示例问题(OpenCV) 2019-04-21
java接口的理解_Java接口的理解 - rabbit_mom的个人空间 - OSCHINA - 中文开源技术交流社区... 2019-04-21
java重用名快捷键_Eclipse 最常用的 10 组快捷键,个个牛逼! 2019-04-21
java中类加载根路径_java中获取类加载路径和项目根路径的5种方法 2019-04-21
Java套接字传文件_Java通过套接字传输多个文件 2019-04-21
递归字符串逆序 java_在Java中使用递归反转字符串 2019-04-21
java推送功能实现原理图_IOS 基于APNS消息推送原理与实现(JAVA后台) - 图文 2019-04-21
java streamencoder_[求助]关于apcche与tomcat 2019-04-21
golang mongodb mysql_分享一个golang+mongodb+vuejs开发的博客程序 gocms 2019-04-21
hive java insert_hive表insert报错 2019-04-21
java 调试dll jna_Java调用dll的实现,JNA框架 | 学步园 2019-04-21
ios php上传视频文件_IOS上传图片 PHP服务器接收并上传 2019-04-21
php redis zrevrange,Redis Zrevrange 命令 2019-04-21