idea离线安装 HTML框架 短视频开发 excel proxy db2 Backbonejs vue插件库 后台系统模板 less用法 jquery each linux源码在线阅读 git登陆命令 mac上传文件到linux java接收数组 mysql教程 python中open java使用mysql 安装java环境 java中的数据类型 java课程 java安装配置 java获取当前线程 java时间格式化 java输出数组 java函数调用 怎么安装linux系统 php连接mssql flash相册制作 球中的小鬼 不寻常的指南针 pr转场特效下载 华为交换机学习指南 福昕阅读器绿色版 迅雷去广告版 arm体系结构与编程 img写盘工具 dos系统下载 oledbconnection cad乘号
当前位置: 首页 > 学习教程  > 编程语言

【leetcode】148.链表归并排序C语言实现O(n log n) 时间复杂度和常数级空间复杂度

2020/9/19 16:25:33 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目出处
题目要求:在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
以下评论来自leetcode @Allen个人感觉受益匪浅,本文在此思路上用C语言实现了对链表的归并排序,并对一些细节做出了补充说明。

bottom-to-up 的归并思路是这样的:先两个两个的 merge,完成一趟后,再 4 个4个的 merge,直到结束。举个简单的例子:[4,3,1,7,8,9,2,11,5,6].

step=1: (3->4)->(1->7)->(8->9)->(2->11)->(5->6)
step=2: (1->3->4->7)->(2->8->9->11)->(5->6)
step=4: (1->2->3->4->7->8->9->11)->(5->6)
step=8: (1->2->3->4->5->6->7->8->9->11)

链表里操作最难掌握的应该就是各种断链啊,然后再挂接啊。在这里,我们主要用到链表操作的两个技术:

merge(l1, l2),双路归并,我相信这个操作大家已经非常熟练的,就不做介绍了。

cut(l, n),可能有些同学没有听说过,它其实就是一种 split 操作,即断链操作。不过我感觉使用 cut 更准确一些,它表示,将链表 l 切掉前 n 个节点,并返回后半部分的链表头。

额外再补充一个 dummyHead 大法,已经讲过无数次了,仔细体会吧。

希望同学们能把双路归并和 cut 断链的代码烂记于心,以后看到类似的题目能够刷到手软。

C语言实现代码

cut操作:

list cut(list head,int n)
{
    int i = 0;
    list res = NULL;//先给res赋值为空指针,否则如果由于链表长度的原因n无效,返回的res就变为了野指针
    while(head)
    {
        i++;
        if(i == n)
        {
            res = head->next;
            head->next = NULL;
            break;
        }
        head = head->next;
    }
    return res;
}

merge

此处注意
①我们并没有另开一个新链表,而是把l1本身当作新链表进行归并。
②此处因为链表第一个元素不确定,所以需要添加一个哑元头节点

list merge(list l1,list l2)//注意传入的参数一定都是没有头节点的
{
    list dummyhead = (list)malloc(sizeof(struct ListNode));
    
    list temp = dummyhead;
    while(l1&&l2)
    {
        if(l1->val < l2->val)
         {
             dummyhead->next = l1;
             l1 = l1->next; 
         }
         else
         {
             dummyhead->next = l2;
             l2 = l2->next;
         }
         dummyhead = dummyhead->next;
    }
    dummyhead->next= l1? l1:l2;
   
    return temp->next;

}

Sort

struct ListNode* sortList(struct ListNode* head)
{
    list dummyhead = (list)malloc(sizeof(struct ListNode));
    dummyhead->next = head;//头结点哑元

    list head_len = head;
    list p = head;
   

    int len = 0;
    while(head_len)
    {
        len++;
        head_len = head_len->next;
    }

    list left;
    list right;
    list tail;

    for(int size = 1;size <= len ;size*=2)
    {
        p = dummyhead->next;
         //p要移到开头,方便接下来的链以另一种size归并排序

        tail = dummyhead;
       //一整条链都归并完了,需要把tail移到哑元处,使得tail->next是一个良好的接口
       //归并的过程中第一个元素的位置会发生改变,所以tail初始状态一定是哑元
      
        while(p)//把所有的都按一种size归并排序,一直到链尾
        {
            left = p;
            right = cut(p,size);
            p = cut(right,size);

            tail->next = merge(left,right);
            //这一步非常关键,用tail->next表示接上下面的条链

           while(tail->next)//接上之后需要把接上的部分跑完,留一个接口接下一段
              tail = tail->next;
        //归并的过程中第一个元素的位置会发生改变,所以一定需要哑元
        }
    }
    return dummyhead->next;
}

有什么问题欢迎在评论区探讨~谢谢大家


本文链接: http://www.dtmao.cc/news_show_200410.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?