- 浏览: 173238 次
- 性别:
- 来自: 济南
文章分类
最新评论
Sort a linked list in O(n log n) time using constant space complexity.
在O(nlogn)的时间复杂度下对一个链表进行排序,通过时间复杂度很容易想到用快排和分治。链表的快排实现比较复杂,这里我们用分治法来实现。代码如下:
在O(nlogn)的时间复杂度下对一个链表进行排序,通过时间复杂度很容易想到用快排和分治。链表的快排实现比较复杂,这里我们用分治法来实现。代码如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; ListNode fast = head; ListNode slow = head; while(fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode node = slow.next; slow.next = null; ListNode left = sortList(head); ListNode right = sortList(node); return merge(left, right); } public ListNode merge(ListNode left, ListNode right) { if(left == null) return right; if(right == null) return left; if(left.val > right.val) { right.next = merge(left, right.next); return right; } else { left.next = merge(left.next, right); return left; } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 340Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 331Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 449Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 509Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 428Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 529Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 859Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 627For a undirected graph with tre ...
相关推荐
JAVA SortList 通用排序类 从网上搜到一个java 对 List 排序的工具,自己改了下 支持 整数 和 浮点数 比较后排序,浮点数小数部分的有点问题,期待大牛帮忙优化。
MFC自带的SortList要实现排序,需要自己做很多工作,此代码简化了与ListCtrl有关的一切操作,尤其是排序
Sort list based on text/numeric/date-time in any column按列表的文本数值时间排序(3KB)
Grasshopper 多条件排序 示例 通过set 以及 sort list 完成多条件排序
8 Remove (Values) From List-删除list中某个值 Remove From List:按照index删除,⼀次删除1个 Remove Values From List:按照value值删除,⼀次可删除多个 ⽰例如2.6 9 Sort List–升序排序 对list做升序排序,⽰...
List sortList = controllerForList.sortList(list, arr1, arr2); 参数1 排序的集合 参数2 排序的字段(与定义字段一致) 可多个 参数3 排序方式(asc desc) 暂时只支持String 和int的排序 可能有些BUG 敬请谅解
列表控件(视图)源代码:sortlist 关键字:sortlist,列表控件(视图)
# SortList 排序列表 android studio 版本 实现了类似与通讯录的效果, 可以多选,如图: ![image](https://raw.githubusercontent.com/jiang111/SortList/master/app/gif/finish.gif) ![image]...
SortList 排序列表 android studio 版本 实现了类似与通讯录的效果, 可以多选,如图:
NULL 博文链接:https://xuedong.iteye.com/blog/1147254
SortList-Project:这是如何按字母顺序对单词列表进行排序
Magic Sort List是一款Mac上的文档编辑软件,Magic Sort List可以帮助用户对大段乱序的文本进行智能排序,Magic Sort List具有革命性的排序引擎,其他排序应用程序可以很好地按字母表排序,但遇到非零填充数字则可能...
对于C++的STL的双向链表,排序算法有的模板并没有实现,因此给出来,大家参考。
ListSort.cs
基于Python的几种基础排序算法,包含冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序。
Sorted-list-for-insersion-sort:插入排序列表Q1
list-sort.py
对TXT文档中的数据进行排序,并把排序完成后的数据写入指定的TXT文件中。
IMDb通过拖放对列表进行排序。 IMDb通过拖放对列表进行排序。 支持语言:English