给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
1、暴力方法，先将链表的值存放到一个数组中，然后对这个数组进行快速排序，然后只需要遍历这个数组，将对应的数组的值赋值给链表的节点即可。但是这样做的话需要开辟空间给数组。
对应的代码：
class Solution {
public ListNode sortList(ListNode head) {
ListNode cur = head;
List<Integer> list = new ArrayList<Integer>(); //临时存放链表的值
while(cur != null){
list.add(cur.val);
cur = cur.next;
}
int[] arr = new int[list.size()];
int i;
for(i = 0; i < arr.length; i++){
arr[i] = list.get(i);
}
sort(arr,0,arr.length - 1); //对数组进行快速排序
/*
遍历链表之后，重新创建链表的操作虽然也可以，但是这样的话就还需要
开辟空间，所以为了减少空间的浪费，直接在原来的链表的基础上修改它
节点的值即可。
*/
cur = head;
//遍历已经排好序的数组，然后构建链表
for(i = 0; i < arr.length; i++){
cur.val = arr[i];
cur = cur.next;
}
return head;
}
public void sort(int[] arr,int low,int high){
if(low < high){
int pivot = getPivot(arr,low,high); //利用三数中值法，从而获取中间枢纽
System.out.println(pivot);
int i = low,j = high - 1;
while(i < j){
/*
必须要从左边开始遍历，找到第一个大于枢纽的数，然后从右边遍历
找到第一个小于枢纽的数，然后将两者的值进行交换。如果两个步骤
交换顺序，那么就会导致快速排序的错误
*/
while(i < j && arr[++i] <= pivot);
while(i < j && arr[--j] >= pivot);
if(i >= j)
break;
swap(arr,i,j);
}
arr[high - 1] = arr[i];
arr[i] = pivot;
sort(arr,low,i - 1);
sort(arr,i + 1,high);
}
}
public void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public int getPivot(int[] arr,int low,int high){
int mid = (low + high) / 2;
if(arr[low] > arr[mid])
swap(arr,low,mid);
if(arr[low] > arr[high])
swap(arr,low,high);
if(arr[mid] > arr[high])
swap(arr,mid,high);
swap(arr,mid,high - 1);
return arr[high - 1];
}
}
运行结果:
2、利用归并排序
但是对于链表来说，利用归并排序，首先我们需要获取中间的节点。怎么实现这一步呢？利用快慢指针就好了，快指针走的是慢指针的2被，此时当快指针走完整个链表的时候，那么慢指针就是终点的位置了。然后进入递归，当链表为空或者只有一个节点的时候，那么就结束递归，进行合并的操作了。
对应的代码：
class Solution {
/*
利用归并排序对链表进行排序
*/
public ListNode sortList(ListNode head) {
return mergeSort(head);
}
public ListNode mergeSort(ListNode head){
if(head != null && head.next != null){
//如果链表不为空，并且不止一个节点的时候，那么就对这个链表进行分割
ListNode cur,pre,tmp;
pre = head;
cur = head;
//通过双指针，从而得到链表的中点
while(cur != null && cur.next != null && cur.next.next != null){
//循环条件必须是这样，因为需要考虑链表的节点的个数是奇数和偶数的情况
pre = pre.next;
cur = cur.next.next;
}
tmp = pre.next;
pre.next = null; //基于上面while循环的判断条件，这一步是必要的，从而将链表彻底变成两条子链表
ListNode left = mergeSort(head);
ListNode right = mergeSort(tmp);
ListNode sorted = merge(left,right);//对两条子链表进行排序,将排好序的
return sorted; //返回排好序的链表的头结点
}else{
//如果链表为空，或者链表只有一个节点的时候，直接将这个节点返回
return head;
}
}
/*
对两条有序链表进行合并的时候，合并时是在其中一条链表上操作的，而不是重
新创建一条链表
*/
public ListNode merge(ListNode head1,ListNode head2){
ListNode cur1,cur2,pre,tmp;
ListNode root = new ListNode(0);
root.next = head1;
pre = root;
cur1 = head1;
cur2 = head2;
while(cur1 != null && cur2 != null){
if(cur1.val < cur2.val){
cur1 = cur1.next;
}else{
tmp = cur2.next;
cur2.next = pre.next;
pre.next = cur2;
cur2 = tmp;
}
/*
这一步是关键，不可以将这一步写在if判断里面，否则就会导致错误
比如当前的值是cur2的值小，如果将pre = pre.next这一步写在if判断
里面，那么最后导致合并的链表缺少某些值
*/
pre = pre.next;
}
if(cur2 != null)
pre.next = cur2;
return root.next;
}
}
运行结果:
但是考虑到ListNode是一个引用类型，那么在方法中对形参修改，会影响到实际的参数，所以原来的代码是这样的，但是结果是错误的，如果有大佬明白错误的原因的话，请指正。
public ListNode sortList(ListNode head) {
mergeSort(head);
return head;
}
public void mergeSort(ListNode head){
if(head != null && head.next != null){
//通过双指针，从而得到链表的中点
ListNode cur,pre,tmp;
pre = head;
cur = head;
while(cur != null && cur.next != null && cur.next.next != null){
pre = pre.next;
cur = cur.next.next;
}
tmp = pre.next;
pre.next = null;
mergeSort(head);
mergeSort(tmp);
ListNode sorted = merge(head,tmp);
}
}
public void merge(ListNode head1,ListNode head2){
ListNode cur1,cur2,pre,tmp;
ListNode root = new ListNode(0);
root.next = head1;
pre = root;
cur1 = head1;
cur2 = head2;
while(cur1 != null && cur2 != null){
if(cur1.val < cur2.val){
cur1 = cur1.next;
}else{
tmp = cur2.next;
cur2.next = pre.next;
pre.next = cur2;
cur2 = tmp;
}
pre = pre.next;
}
if(cur2 != null)
pre.next = cur2;
head1 = root.next;
}