[链表]-单链表排序

方法一：利用快速排序实现单链表的排序（力扣上出现超时），牛客上好使

public ListNode singleListSort(ListNode head){
	if(head == null || head.next == null){
		return head;
	}
	ListNode cur = head;
	while(cur.next != null){
		cur = cur.next;
	}
	quickSort(head,cur);
	return head;
}

public void quickSort(ListNode low,ListNode high){
	if(low == null || low.next == null || low == high){
		return; //返回值是空的话，直接return就行，不要return null;报错
	}
	int pivot = low.val;
	ListNode i = low.next;
	ListNode i_pre = low;
	ListNode j = low.next;
	while(j != high.next){
		if(j.val < pivot){
			swap(i,j);
			i_pre = i;
			i =i.next;
		}
		j = j.next;
	}
	swap(low,i_pre);
	//递归
	quickSort(low,i_pre);
	quickSort(i,high);
}

public void swap(ListNode a,ListNode b){
	int temp = a.val;
	a.val = b.val;
	b.val = temp;
}

方法二：归并排序实现单链表排序

public ListNode listSort(ListNode head){
	if(head == null || head.next == null){
		return head;
	}
	//快慢指针找到mid
	ListNode fast = head.next;
	ListNode slow = head;
	while(fast != null && fast.next != null){
		slow = slow.next;
		fast = fast.next.next;
	}
	//循环结束后slow就是mid
	ListNode tmp = slow.next;
	slow.next = null;
	//递归分解
	ListNode left = listSort(head);
	ListNode right = listSort(tmp);
	//合并
	ListNode dummy= new ListNode(-1);
	ListNode cur = dummy;
	while(left != null && right != null){
		if(left.val < right.val){
			cur.next = left;
			left = left.next;
		}else{
			cur.next = right;
			right = right.next;
		}
		cur = cur.next;
	}
	//循环结束后，left或者right有一个未遍历完
	cur.next = (left != null ? left : right);
	return dummy.next;
}