LeetCode实战：排序链表
背景
- 为什么你要加入一个技术团队？
- 如何加入 LSGO 软件技术团队？
- 我是如何组织“算法刻意练习活动”的？
- 为什么要求团队的学生们写技术Blog
题目英文
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
题目中文
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
算法实现
利用归并的思想，递归地将当前链表分为两段，然后merge，分两段的方法是使用 fast-slow 法，用两个指针，一个每次走两步，一个走一步，直到快的走到了末尾，然后慢的所在位置就是中间位置，这样就分成了两段。
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val = x; }* }*/public class Solution
{public ListNode SortList(ListNode head){if (head == null)return null;return MergeSort(head);}private ListNode MergeSort(ListNode node){if (node.next == null){return node;}ListNode fast = node;ListNode slow = node;ListNode cut = null;while (fast != null && fast.next != null){cut = slow;slow = slow.next;fast = fast.next.next;}cut.next = null;ListNode l1 = MergeSort(node);ListNode l2 = MergeSort(slow);return MergeTwoLists(l1, l2);}private ListNode MergeTwoLists(ListNode l1, ListNode l2){ListNode pHead = new ListNode(int.MaxValue);ListNode temp = pHead;while (l1 != null && l2 != null){if (l1.val < l2.val){temp.next = l1;l1 = l1.next;}else{temp.next = l2;l2 = l2.next;}temp = temp.next;}if (l1 != null)temp.next = l1;if (l2 != null)temp.next = l2;return pHead.next;}
}
实验结果
- 状态：通过
- 16 / 16 个通过测试用例
- 执行用时: 124 ms, 在所有 C# 提交中击败了 100.00% 的用户
- 内存消耗: 29 MB, 在所有 C# 提交中击败了 25.00% 的用户
相关图文
1. “数组”类算法
- LeetCode实战：三数之和
- LeetCode实战：最接近的三数之和
- LeetCode实战：求众数
- LeetCode实战：缺失的第一个正数
- LeetCode实战：快乐数
- LeetCode实战：寻找两个有序数组的中位数
- LeetCode实战：盛最多水的容器
- LeetCode实战：删除排序数组中的重复项
- LeetCode实战：搜索旋转排序数组
- LeetCode实战：螺旋矩阵
- LeetCode实战：螺旋矩阵 II
- LeetCode实战：买卖股票的最佳时机
- LeetCode实战：买卖股票的最佳时机 II
2. “链表”类算法
- LeetCode实战：两数相加
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
3. “栈”类算法
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
4. “队列”类算法
- LeetCode实战：设计循环双端队列
- LeetCode实战：滑动窗口最大值
- LeetCode实战：整数反转
- LeetCode实战：字符串转换整数 (atoi)
5. “递归”类算法
- LeetCode实战：爬楼梯
6. “位运算”类算法
- LeetCode实战：只出现一次的数字
- LeetCode实战：格雷编码
7. “字符串”类算法
- LeetCode实战：反转字符串
- LeetCode实战：翻转字符串里的单词
- LeetCode实战：最长公共前缀
- LeetCode实战：字符串相加
- LeetCode实战：字符串相乘
8. “树”类算法
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：二叉树中的最大路径和
- LeetCode实战：将有序数组转换为二叉搜索树
9. “哈希”类算法
- LeetCode实战：两数之和
10. “排序”类算法
- LeetCode实战：合并两个有序数组
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
11. “搜索”类算法
- LeetCode实战：搜索二维矩阵
- LeetCode实战：子集
12. “动态规划”类算法
- LeetCode实战：最长回文子串
- LeetCode实战：最大子序和
- LeetCode实战：不同路径
13. “回溯”类算法
- LeetCode实战：全排列
14. “数值分析”类算法
- LeetCode实战：回文数
- LeetCode实战：x 的平方根
相关文章：
技术图文：双指针在链表问题中的应用
背景 最近这段时间团队在进行算法刻意练习活动，我带着同学们刷 leetcode 的“腾讯精选练习（50）题”，参见：我是如何组织“算法刻意练习活动”的？ 在做题的过程中，同学们讨论比较多的是链表中遇…
[BuildRelease]build number / id
build number， 也称为build id， 在build release的流程中唯一标示一个build，也是正式的产品的product version 和file version后两位（Major.minor.xxx.xxx）的来源，可以使用合适的方法将build number转化到p…
Windows Azure Storage (25) Azure Append Blob
《Windows Azure Platform 系列文章目录》 在笔者之前的文章中，我们介绍了Azure Blob 有两种：Block Blob和Page Blob。 在这里笔者介绍Blob的第三种：Append Blob。 概念： 1.Append Blob概念类似于Block Blob，因为都是由…
学python培训到底能干嘛
Python是在人工智能领域发挥着很重要的作用的，现在依旧有很多人对Python这项技术不是很了解，学Python培训到底能干嘛?下面小编来为大家做下详细的介绍。 python其实并不难学，对于初学者和完成普通任务，Python语言是非常简单易用的…
使用VB.NET加快代码开发速度
以前在学校时，编写代码都是使用C#，习惯了C#的代码习惯，等工作后由于工作需要逐渐的开始采用了VB.NET开发项目，渐渐地喜欢上了VB.NET，现在我就罗列一些VB.NET加速代码开发的方法。 一、智能感知 做.NET开发的许多人都知…
技术图文：举例详解Python中 split() 函数的使用方法
背景 这篇文章主要介绍Python中的split()函数的使用方法，split()函数通常用于将字符串切片并转换为列表，需要的朋友可以参考一下。 技术分析 Python中有split()和os.path.split()两个函数，具体作用如下： split()：拆…
Burning
转载于:https://www.cnblogs.com/kuiyuan/archive/2011/09/02/2163621.html
UI设计工作好找吗?有哪些面试技巧?
最近有很多学习UI设计的学员，想要了解UI设计学成之后是否好找工作?对于后期的面试有哪些技巧?下面小编整理的这些希望可以帮助到大家，来看看下面的详细介绍。 UI设计工作好找吗?有哪些面试技巧? 作品：很多初级小白的问题所在就是缺少大量…
刻意练习：Python基础 -- Task10. 类与对象
背景 我们准备利用17天时间，将 “Python基础的刻意练习” 分为如下任务： Task01：变量、运算符与数据类型（1day）Task02：条件与循环（1day）Task03：列表与元组（…
CentOS 7更新时出现Multilib version problems
这两天在更新CentOS7系统时，出现了Multilib version problems错误，执行命令： # yum update 出现了的错误信息： .... ---> Package libcap-ng.i686 0:0.7.5-4.el7 will be installed ---> Package libstdc.i686 0:4.8.5-16.e…
HTTP 错误 404.13 - Not Found 请求筛选模块被配置为拒绝超过请求内容长度的请求。...
把以下内容加在web.config的<system.webServer>节点 <security><requestFiltering ><requestLimits maxAllowedContentLength"1024000000" ></requestLimits></requestFiltering></security> 上述中maxAllowedContentLeng…
APP自动化测试过程概述
对于Android App的自动化测试框架的使用，其实在很多书上面都会有说明，我们可以先来看一个常用的自动化测试实例，先不说框架，主要是测试用户操作的模拟、执行结果的判断，以便获得对测试自动化的理解与认识。 案例需求如…
MFC最小化到系统托盘
在VC中，想实现将MFC最小化到系统托盘，需要调用NOTIFYICONDATA类，并注册相应的消息，以下详细讲解如何实现： 第一步，声明一个NOTIFYICONDATA类，也就是NOTIFYICONDATA NotifyIcon;该句可以放在Dlg类…
资料分享：推荐一本《简单粗暴TensorFlow 2.0》开源电子书！
背景 本开源电子书是一篇精简的 TensorFlow 2.0 入门指导，基于 TensorFlow 的 Eager Execution（动态图）模式，力图让具备一定机器学习及 Python 基础的开发者们快速上手 TensorFlow 2.0。 本开源电子书的所有代码基于 TensorFlow…
JS设计模式-观察者模式
观察者（又称发布订阅）模式定义了对象间的一种一对多的依赖关系，以便一个对象的状态发生变化时，所有依赖于它的对象都得到通知并自动刷新。原文链接 应用场景 当用户在网页执行一些操作（如点击）后就需要执行…
如何理解JS的单线程?
JS本质是单线程的。也就是说，它并不能像JAVA语言那样，两个线程并发执行。 但我们平时看到的JS，分明是可以同时运作很多任务的，这又是怎么回事呢? 首先，JS的代码，大致分为两类，同步代码和异步代…
Fedora 14下安装使用rarlinux
安装Fedora 14后，其默认情况下不能解压RAR文档，因为系统自带的解压软件不支持RAR格式文档，但由于经常要用到RAR文档，因此就必须安装一个RAR软件。Linux版的RAR下载链接： http://www.rarlab.com/download.htm 以rarlinu…
技术图文：如何利用 Python 做一个简单的定时器类？
背景 今天在B站上看有关 Python 最火的一个教学视频，零基础入门学习 Python，这也是我们 Python基础刻意练习活动 的推荐视频教程。 在学习魔法方法的时候，有一节视频是制作一个简单的定时器，基本要求如下： 定制一个计…
20、C#里面方法的创建和显示
在C#里面，和Java也是一样的，都是可以创建方法的。这里所说的方法，就是其它编程语言里面的函数、子程序、过程等。创建的方法有两种：一种是没有返回值的方法。一种是有返回值的方法。无论是哪种方法，其实都是很简单的。…
优秀的Java程序员应具备哪些编程技术?
想要成为一名合格的java程序猿，需要学习的知识是有很多的，但是基础知识一定要非常牢固，基础不牢固的程序员，随时都会被新的知识和技术所淘汰，下盘不稳风一吹就倒，那么具体作为一个优秀的Java程序员应具备哪…
asp.net 后台事件掉用前台js
在下面的例子中，我们在一个 .aspx 文件中声明了一个 TextBox 控件和一个 Label 控件。当您更改了 TextBox 中的值，并且在 TextBox 外单击时，change 子例程就会被执行。change 子例程会向 Label 控件写一条文本： <script runat&…
Android -- 利用Broadcast开启Service
Broadcast和Service都是Android四大组建之一的。 这里的广播是动态的，自己注册的一个广播。 这种最典型的用法就是利用开机广播，然后再起自己的服务，也就是在Android手机中做到开启启动。 Service与Broadcast …
资料分享：推荐一本《李宏毅机器学习》开源电子书！
背景 今天在 github 上看到了 datawhale 发布的 李宏毅机器学习笔记。 https://datawhalechina.github.io/leeml-notes 其目录如下： P1 机器学习介绍P2 为什么要学习机器学习P3 回归P4 回归-演示P5 误差从哪来？P6 梯度下降P7 梯度下降（用…
Python 中常见的配置文件写法
相信学习Python或者正在进行Python工作的小伙伴都会有一个疑问，为什么要写配置文件呢?在开发过程中，我们常常会用到一些固定参数或者是常量。对于这些较为固定且常用到的部分，往往会将其写到一个固定文件中，避免在不同的模块代码…
技术图文：Python描述符 (descriptor) 详解
背景 今天在B站上学习“零基础入门学习Python”这门课程的第46讲“魔法方法：描述符”，这也是我们组织的 Python基础刻意练习活动 的学习任务，其中有这样的一个题目。 练习要求： 先定义一个温度类，然后定义两个描述符…
[转]自定义hadoop map/reduce输入文件切割InputFormat
本文转载自：http://hi.baidu.com/lzpsky/blog/item/99d58738b08a68e7b311c70d.html hadoop会对原始输入文件进行文件切割，然后把每个split传入mapper程序中进行处理，FileInputFormat是所有以文件作 为数据源的InputFormat实现的基类&…
使用深度学习检测DGA（域名生成算法）——LSTM的输入数据本质上还是词袋模型...
from:http://www.freebuf.com/articles/network/139697.html DGA（域名生成算法）是一种利用随机字符来生成C&C域名，从而逃避域名黑名单检测的技术手段。例如，一个由Cryptolocker创建的DGA生成域xeogrhxquuubt.com，如…
学习Python开发培训有用吗
学习Python开发培训有用吗?这是目前很多人都比较关注的一个问题，Python语言在最近几年是广受IT互联网行业关注的， 下面我们就针对这问题来详细的分析一下。 学习Python开发培训有用吗?Python是被广泛使用的高级编程语言，Python解释器本身几…
Web性能优化实践——应用层性能优化
随着公司项目的进一步推广，用户数量的增加，已经面临着单台服务器不能负载的问题。 这次的优化由于时间关系主要分两步走，首先优化应用层代码以提高单台服务器的负载和吞吐率。之后再进行分表，引入队列、MemCached等分布式应用。 项…
技术图文：Python魔法方法之属性访问详解
背景 今天在B站学习“零基础入门学习 Python”中的第45节“魔法方法：属性访问”，这也是我们组织的 Python基础刻意练习活动 的学习任务，其中有这样的一个题目。 练习要求： 写一个矩形类，默认有宽和高两个属性。如果…