使用常数个空间对链表进行排序 Sort List
问题:
Sort a linked list in O(n log n) time using constant space complexity.
解决:
① 本题要求使用一种时间复杂度为O(n log n),空间复杂度为常量。可以根据如下表格进行考虑:
本题采用归并排序。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
【注】归并排序的基本思想
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
综上可知:
归并排序其实要做两件事:
(1)“分解”——将序列每次折半划分。
(2)“合并”——将划分后的序列段两两合并后排序。
对数组而言,归并排序的空间复杂度为O(N), 需要O(N)的额外空间来容纳数组,来表示归并后的顺序。但是,对于链表而言,可以省下这部分空间的开销,只需要改变节点的next指针的指向,就可以表示新的归并后的顺序了,所以空间复杂度陡然降到了O(1)。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution { //8ms
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode midNode = getMidNode(head);
ListNode head1 = midNode.next;
midNode.next = null;
return mergeList(sortList(head),sortList(head1));//递归获取两个分解的链表
}
public ListNode getMidNode(ListNode head){//获取中间节点
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode mergeList(ListNode h1,ListNode h2){//合并两有序链表
ListNode header = new ListNode(-1);
ListNode cur = header;
while(h1 != null && h2 != null){
if (h1.val <= h2.val) {
cur.next = h1;
h1 = h1.next;
}else{
cur.next = h2;
h2 = h2.next;
}
cur = cur.next;
}
cur.next = (h1 == null) ? h2 : h1;
return header.next;
}
}
② 在discuss中看到的。感觉排的挺复杂的,有点看不懂。。。
class Solution {//3ms
public ListNode sortList(ListNode head) {
sortList(head, null);
return head;
}
public void sortList(ListNode start, ListNode end) {
if (start != end) {
ListNode node = partition(start, end);
sortList(start, node);
while (node.next != end && node.val == node.next.val)
node = node.next;
sortList(node.next, end);
}
}
private ListNode partition(ListNode start, ListNode end) {
if (start == end)
return null;
ListNode left = start, right = start.next;
while (right != end) {
if (right.val < start.val) {
left = left.next;
swap(left, right);
}
right = right.next;
}
swap(start, left);
return left;
}
private void swap(ListNode a, ListNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
}
【注】测试函数
public static void main(String[] args){ ListNode l1 = new ListNode(2); ListNode l2 = new ListNode(3); ListNode l3 = new ListNode(4); ListNode l4 = new ListNode(7); ListNode l5 = new ListNode(1); ListNode l6 = new ListNode(5); ListNode l7 = new ListNode(9); l1.next = l2; l2.next = l3; l3.next = l4; l4.next = l5; l5.next = l6; l6.next = l7; l1 = sortList(l1); printList(l1); } public static void printList(ListNode x){ if (x != null){ System.out.print(x.val + " "); while(x.next != null) { System.out.print(x.next.val + " "); x = x.next; } System.out.println(); } }
转载于:https://my.oschina.net/liyurong/blog/1563445