本文描述了LeetCode 148题 sort-list 的解法。
题目描述如下:
Sort a linked list in O(n log n) time using constant space complexity.
题目要求我们在O(n log n)时间复杂度下完成对单链表的排序,我们知道平均时间复杂度为O(n log n)的排序方法有快速排序、归并排序和堆排序。而一般是用数组来实现二叉堆,当然可以用二叉树来实现,但是这么做太麻烦,还得花费额外的空间构建二叉树,于是不采用堆排序。
故本文采用快速排序和归并排序来对单链表进行排序。
快速排序
在一般实现的快速排序中,我们通过首尾指针来对元素进行切分,下面采用快排的另一种方法来对元素进行切分。
我们只需要两个指针p1和p2,这两个指针均往next方向移动,移动的过程中保持p1之前的key都小于选定的key,p1和p2之间的key都大于选定的key,那么当p2走到末尾时交换p1与key值便完成了一次切分。
图示如下:
代码如下:
public ListNode sortList(ListNode head) {
//采用快速排序
quickSort(head, null);
return head;
}
public static void quickSort(ListNode head, ListNode end) {
if (head != end) {
ListNode node = partion(head, end);
quickSort(head, node);
quickSort(node.next, end);
}
}
public static ListNode partion(ListNode head, ListNode end) {
ListNode p1 = head, p2 = head.next;
//走到末尾才停
while (p2 != end) {
//大于key值时,p1向前走一步,交换p1与p2的值
if (p2.val < head.val) {
p1 = p1.next;
int temp = p1.val;
p1.val = p2.val;
p2.val = temp;
}
p2 = p2.next;
}
//当有序时,不交换p1和key值
if (p1 != head) {
int temp = p1.val;
p1.val = head.val;
head.val = temp;
}
return p1;
}
归并排序
归并排序应该算是链表排序最佳的选择了,保证了最好和最坏时间复杂度都是nlogn,而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)。
归并排序的一般步骤为:
- 将待排序数组(链表)取中点并一分为二;
- 递归地对左半部分进行归并排序;
- 递归地对右半部分进行归并排序;
- 将两个半部分进行合并(merge),得到结果。
首先用快慢指针(快慢指针思路,快指针一次走两步,慢指针一次走一步,快指针在链表末尾时,慢指针恰好在链表中点)的方法找到链表中间节点,然后递归的对两个子链表排序,把两个排好序的子链表合并成一条有序的链表。
代码如下:
public ListNode sortList(ListNode head) {
//采用归并排序
if (head == null || head.next == null) {
return head;
}
//获取中间结点
ListNode mid = getMid(head);
ListNode right = mid.next;
mid.next = null;
//合并
return mergeSort(sortList(head), sortList(right));
}
/**
* 获取链表的中间结点,偶数时取中间第一个
*
* @param head
* @return
*/
private ListNode getMid(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//快慢指针
ListNode slow = head, quick = head;
//快2步,慢一步
while (quick.next != null && quick.next.next != null) {
slow = slow.next;
quick = quick.next.next;
}
return slow;
}
/**
*
* 归并两个有序的链表
*
* @param head1
* @param head2
* @return
*/
private ListNode mergeSort(ListNode head1, ListNode head2) {
ListNode p1 = head1, p2 = head2, head;
//得到头节点的指向
if (head1.val < head2.val) {
head = head1;
p1 = p1.next;
} else {
head = head2;
p2 = p2.next;
}
ListNode p = head;
//比较链表中的值
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
p.next = p1;
p1 = p1.next;
p = p.next;
} else {
p.next = p2;
p2 = p2.next;
p = p.next;
}
}
//第二条链表空了
if (p1 != null) {
p.next = p1;
}
//第一条链表空了
if (p2 != null) {
p.next = p2;
}
return head;
}
参考文档:
Java实现单链表的快速排序和归并排序的更多相关文章
-
Java实现单链表的各种操作
Java实现单链表的各种操作 主要内容:1.单链表的基本操作 2.删除重复数据 3.找到倒数第k个元素 4.实现链表的反转 5.从尾到头输出链表 6.找到中间节点 7.检测链表是否有环 8.在 ...
-
java实现单链表的增删功能
JAVA 实现单链表的增删功能 package linked; class LinkedTable{ } public class LinkedTableTest { public static vo ...
-
JAVA数据结构——单链表
链表:一. 顺序存储结构虽然是一种很有用的存储结构,但是他有如下几点局限性:1. 因为创造线性表的时候已经固定了空间,所以当需要扩充空间时,就需要重新创建一个地址连续的更大的存储空间.并把原有的数据元 ...
-
使用java实现单链表(转载自:https://www.cnblogs.com/zhongyimeng/p/9945332.html)
使用java实现单链表----(java中的引用就是指针)转载自:https://www.cnblogs.com/zhongyimeng/p/9945332.html ? 1 2 3 4 5 6 7 ...
-
Java: 实现顺序表和单链表的快速排序
快速排序 快速排序原理 快速排序(Quick Sort)的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可对这两部分记录继续进行排序,以达到 ...
-
148. Sort List (java 给单链表排序)
题目:Sort a linked list in O(n log n) time using constant space complexity. 分析:给单链表排序,要求时间复杂度是O(nlogn) ...
-
用Java实现单链表的基本操作
笔试题中经常遇到单链表的考题,下面用java总结一下单链表的基本操作,包括添加删除节点,以及链表转置. package mars; //单链表添加,删除节点 public class ListNode ...
-
java实现单链表常见操作
一.概述: 本文主要总结单链表常见操作的实现,包括链表结点添加.删除:链表正向遍历和反向遍历.链表排序.判断链表是否有环.是否相交.获取某一结点等. 二.概念: 链表: 一种重要的数据结构,HashM ...
-
数据结构——Java实现单链表
一.分析 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.链表中的数据是以结点来表示的,每个结点由元素和指针构成.在Java中,我们可以将单链表定义成一个类,单链表的基 ...
随机推荐
-
A new comer playing with Raspberry Pi 3B
there are some things to do for raspberry pi 3b for the first time: 1, connect pi with monitor/KB/mo ...
-
新浪微博AppKey大集合(share)
本文转自:http://blog.sina.com.cn/s/blog_9e1ea13a01017y3n.html ------------------------------------------ ...
-
C#中的lock关键字有何作用
作为C#的程序员来说,在遇到线程同步的需求时最常用的就是lock关键字.但如何正确并有效地使用lock,却是能否高效地达到同步要求的关键.正因为如此,程序员需要完全理解lock究竟为程序做了什么. 所 ...
-
linux rwxrwxrwt文件夹属性
/tmp 的permission是rwxrwxrwt chmod 0777 /abc rwxrwxrwx chmod 777 /abc rwxrwxrwx chmod 17 ...
-
esriFeatureType与esriGeometryType的区别与联系
esriFeatureType通常用来表示数据的存储结构,即物理层: esriGeometryType通常用来表示数据的几何形状,即表现层. esriGeometryType枚举类型详解 常量 值 对 ...
-
[Linux]学习笔记(4)-su及passwd的用法介绍
(1)su su命令用于将当前的用户切换到一个指定的用户.语法为: su - user_name 如果用户利用telnet方式远程登录,是不能直接以root账户登录的,也就是说在使用telnet登录服 ...
-
C/C++代码检视实例
相关文章链接如下: 微软过桥问题与测试人员素养 等价类分法 新解 测试用例设计中的NP难题 90%程序员写不出无BUG的二分查找程序? C/C++代码检视要点 4.1 代码检视 ...
-
Unity 脚本中update,fixedupdate,lateupdate等函数的执行顺序
结论 通过一个例子得出的结论是:从先到后被执行的函数是 Awake->Start->FixedUpdate->Update->LateUpdate->OnGUI. 示例 ...
-
数据结构与算法 —— 链表linked list(02)
我们继续来看链表的第二道题,来自于leetcode: 两数相加 给定两个非空链表来代表两个非负整数,位数按照逆序方式存储,它们的每个节点只存储单个数字.将这两数相加会返回一个新的链表. 你可以假设除了 ...
-
.NET开发微信小程序-获取OpenId
注:获取当前用户信息只需要用GetUserInfo这个方法就行.这里就不需要提了 前端代码: CallBack:回调函数 function GetOpenID(CallBack){ var appIn ...