2014
07-18

# LeetCode-Sort List 链表排序

### Sort List

Sort a linked list in O(n log n) time using constant space complexity.

，只是实现比下面这个有些复杂。

1. 归并排序实现

public class MergetSortList {

public static  ListNode sortList(ListNode head) {
//用快慢指针找到中间节点
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode list2 = slow.next;
slow.next = null;
list2 = sortList(list2);
}

private static ListNode merge(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
//连接每个节点，只更换指针，因此空间复杂度为O(1)
while(list1 != null && list2 != null){
if(list1.val < list2.val){
last.next = list1;
list1 = list1.next;
}else{
last.next = list2;
list2 = list2.next;
}
last = last.next;
}
//最后剩余的部分，直接连接起来即可
if(list1 != null) last.next = list1;
else if(list2 != null) last.next = list2;
}

public static void main(String[] args) {
ListNode l1 = new ListNode(8);
ListNode l2 = new ListNode(7);
ListNode l3 = new ListNode(6);
ListNode l4 = new ListNode(5);
ListNode l5 = new ListNode(4);
ListNode l6 = new ListNode(3);

l1.next = l2;
l2.next = l3;
l3.next = l4;
l4.next = l5;
l5.next = l6;

l1 = sortList(l1);

while(l1 != null){
System.out.print(l1.val + " ");
l1 = l1.next;
}
}
}

2.快速排序实现

//以end节点作为pivot进行划分，返回划分的节点的前一个节点
public static ListNode partition(ListNode head, ListNode end){
int pivot = end.val;
ListNode lastSmallNode = null;
if(lastSmallNode == null) lastSmallNode = head;
else lastSmallNode = lastSmallNode.next;
int tmp = lastSmallNode.val;
}
}
//有可能是划分的节点就是第一个，此时返回null
if(lastSmallNode == null){
return null;
}else{
end.val = lastSmallNode.next.val;
lastSmallNode.next.val = pivot;
return lastSmallNode;
}
}

public  static void quickSort(ListNode head, ListNode end){
if( head == null || head == end || end == null || head.next == null) return;
//空表示，划分点是第一个位置
if(mid == null)
//如果划分点是最后一个位置，就无需再排序
else if(mid != end && mid.next != null && mid.next != end)
quickSort(mid.next.next, end);
}

public static  ListNode sortList(ListNode head) {