[Leetcode] Sort List (Java)

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

O(n log n)时间复杂度的园地链表排序，归并排序

public class Solution {
    public ListNode sortList(ListNode head) {
		head = mergeSort(head);
		return head;
	}
	private ListNode mergeSort(ListNode head) {
	    
		if(head==null||head.next==null)
			return head;
			
		ListNode slow=head;
		ListNode fast=head;
		ListNode prev=head;
		
		while(fast!=null&&fast.next!=null){
			fast=fast.next.next;
			prev=slow;
			slow=slow.next;
		}
		prev.next=null;
		
		ListNode head1=mergeSort(head);
		ListNode head2=mergeSort(slow);
		
		return merge(head1,head2);
	}
	private ListNode merge(ListNode head1, ListNode head2) {
	    
		ListNode ret = new ListNode(-1);
		ListNode cur = ret;
		
		while(head1!=null&&head2!=null){
			if(head1.val<head2.val){
				cur.next=head1;
				cur=cur.next;
				head1=head1.next;
			}else {
				cur.next=head2;
				cur=cur.next;
				head2=head2.next;
			}
		}
		
		if(head1!=null)
			cur.next=head1;
		else if(head2!=null)
			cur.next=head2;
			
		return ret.next;
	}
}